215. Kth Largest Element in an Array.md

215. Kth Largest Element in an Array

思路

给定一个数组, 要求返回其中第k大的数. 这应该属于常考的面试题了, 务必掌握. 有两个基本的思路: 快排划分的思想和最大(小)堆.

思路一、快排划分

我们回忆一下快排中的partition函数: 每次先(任意)确定一个中枢值pivot，然后遍历其他所有的数字，像这道题从大往小排的话，就把大于中枢点的数字放到左半边， 把小于中枢点的放在右半边，这样中枢点是整个数组中第几大的数字就确定了，虽然左右两部分各自不一定是完全有序的.

所以我们只需要调用partition函数,

• 若得到pivot的最终位置pos刚好就是k-1, 那直接返回nums[k-1];
• 若得到的pos比k-1小, 那在pos右边继续调用partition;
• 否则, 在pos左边继续调用partition.

其实STL中nth_element已经帮我们实现了上述过程, 注意学习使用:

nth_element(vc.begin(), vc.begin()+5, vc.end(), cmp); // 没有返回值

nth_element只保证第n(从0开始)个元素是位于最终排序位置的, 但其左右两边的元素则不一定有序.

时间复杂度平均O(n)（最坏O(n^2)），空间复杂度O(1)

• 平均时间复杂度粗略证明：假设每次都是对半划分，那么第一次划分我们需要遍历约n个数，第二次需要遍历约n/2个数，... 所以总的遍历次数大概就是 n + n/2 + n/4 + n/8 + ...，用一个等比序列求和可得上式的极限（n很大时）为2n。所以这个平均时间复杂度是与k具体多少无关的，例如当k=n/2时还是这个复杂度，即求中位数的平均复杂度也是O(n)。
• 可以先将nums顺序随机打乱，这样就不会出现最坏时间复杂度的情况。

思路二、堆

用最小堆, 维护一个大小为k的最小堆(实际不是堆是个二叉树)，新来一个元素后如果大小超过了k就去掉top元素（是最小的）即可, 到最后堆里就是最大的k个数，堆顶为第k大的数。

由于堆大小为k，初始建堆时间复杂度是线性的即O(k)，后面删除堆顶元素和插入新元素时间都是O(logk)，所以总的时间复杂度是O(nlogk)；空间复杂度O(k)

也可以用最大堆，用最大堆的话需要将所有元素都进堆，然后再删除堆顶的元素 k-1 次。 初始建堆复杂度O(n)，再加上 k-1 次删除操作，所以总的时间复杂度为O(n + klogn)；堆大小为n，所以空间复杂度O(n)。 所以但当n很大时是用最大堆不合理的，将消耗大量空间。

在STL中, priority_queue和multiset都可用来作为最小(大)堆, 代码以前者为例, 用multiset可以参考此处

注意用priority_queue如何实现最大(小)堆, 即如何自定义比较方法(和sort、nth_element、partial_sort函数自定义比较函数写法不一样)

其实, STL里有一个函数可以实现部分排序即partial_sort, 给定位置k, 该函数会将位置k前(不包含k)的元素排好序, 而k及之后元素则不一定有序.

建议详读讨论区总结

思路三、桶排序

如果数组里的元素的范围是固定的（有限的），还可以用桶排序。

C++

思路一

class Solution {
private:
    int partition(vector<int> &nums, int low, int high){
        int i = low, j = high;
        int pivot = nums[low];
        
        while(i < j){
            while(i < j && nums[j] < pivot) j--;
            nums[i] = nums[j]; // 将比pivot大的元素移到pivot左边
            
            while(i < j && nums[i] >= pivot) i++;
            nums[j] = nums[i]; // 将比pivot小的元素移到pivot右边
        }
        
        nums[i] = pivot;
        return i;
    }
public:
    int findKthLargest(vector<int>& nums, int k){
        int low = 0, high = nums.size() - 1, pos;
        while(true){
            pos = partition(nums, low, high);
            
            if(pos == k - 1) return nums[pos];
            if(pos < k - 1) low = pos + 1;
            else high = pos - 1;
        }
    }
};

思路一STL版

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // greater和less都重载了操作符()
        nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), greater<int>());
        return nums[k - 1];
    }
};

思路二

class Solution {
static bool comp_func(const int &a, const int &b){
    return a > b;
}
struct comp_class{
  bool operator()(const int &a, const int &b){
    return a > b;
  }
};
public:
    int findKthLargest(vector<int>& nums, int k){
        // 以下三种写法都是可以的. 默认为最大堆: priority_queue<int, vector<int> > pq;
        // priority_queue<int, vector<int>, greater<int>> pq; 
        // priority_queue<int, vector<int>, bool (*)(const int &a, const int &b) > pq(comp_func);
        priority_queue<int, vector<int>, comp_class > pq;

        for (int num : nums) {
            pq.push(num);
            if (pq.size() > k) {
                pq.pop();
            }
        }
        return pq.top();
    }
};

思路二STL版

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        partial_sort(nums.begin(), nums.begin() + k, nums.end(), greater<int>());
        return nums[k - 1];
    }
};