数组中第N大元素的问题，如果有重复怎么办？

Question

题目的前提是数组中的元素不重复吗？

Answer 1

liuyubobobo 2017-07-14 01:32:31

非常好的问题。这其实是一个问题的定义问题。我使用的是自然语言来描述这个问题，但其实有很多边界和概念是模糊的。比如对于数组[1, 1, 3, 3, 5], 如果问第2大的元素是谁？通常我们按照生活经验理解，应该是3；但有的时候，我们编程要完成的任务，其实是忽视这种重复，取出第2个元素，即索引为1的元素（从0开始索引），此时对于这个数组，答案是1。

所以，搞清楚要解决的问题，永远是非常非常重要的。这也是为什么我在《玩儿转算法面试》的课程中，一直强调，对于面试的算法问题，一定要和面试官明确问题的细节，定义，以及边界在哪里。这一点和正确的解决问题是一样重要。因为在实际工作中，我们就是要不停的和项目组或者同事或者老板讨论，我们究竟要解决什么问题：从整个工程要解决什么问题；到我今天编写一个函数一个方法，要解决一个什么问题。这个“要解决的问题”，是不能范范而谈的。你这个post提出的问题就是一个非常好的例子。我们说：我们要解决的问题是“找出第N大元素”都是远远不够的。有重复元素怎么办？N大于元素总个数怎么处理？N等于负数又该怎么处理。N是从0开始计算还是从1开始计算，换句话说，我们的最大的元素是第0个元素还是第1个元素？如果是第1个元素的话，N为0又要怎么处理？数组为空怎么处理，等等等等。这些问题，都最好在具体编程之前定义清楚，否则就会为日后你所写的程序运用到更大的系统中造成潜在的隐患。

当我们明确了问题以后，有的时候解决反而是容易的。对上面的问题而言，如果我们定义的问题，要求最终答案为3，那么我们做一下去重，再进行select算法就好了；如果要求最终答案为1；我们原数组直接进入select算法就好了：）

• 提问者 慕田峪2868672 #1

  非常感谢！

• 慕粉3169703 #2

  老师，请问您说的去重是指在排序的过程中去重吗，如果用这种方式，和把整个数组元素快速排序之后再进行去重计数查找第N大的元素相比，哪个效率更高？

• liuyubobobo 回复 慕粉3169703 #3

  可以使用哈希表去重，复杂度是O(n)；排序后去重，复杂度是O(nlogn)。从复杂度分析的角度，排序后去重性能更差。但logn的差距，在大多数情况下是完全可以接受的：）