215 - Kth Largest Element in an Array

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Hide Tags
Divide and Conquer Heap

解法丰富的一道题， 分治，hash，最小堆，最大堆都可以。

最大堆就是全部丢到最大堆里头，每次扔掉堆顶并计数，直到第k个，
简单，但每次重新reheapify费时间，应该是O((n+k)lgn)，实际跑出来是 1160 ms，真壮观。。。

最小堆要快一些，堆的大小为k，最终的对顶就是第k大的值，
过程是如果遇到比堆顶大的，就替换掉对顶重新reheapify。复杂度大概是 O(nlgk)，最终跑出来是280 ms，也不少。

hash表的做法是用map来统计所有数组里的值（并自动排序），然后找到需要的值即可，代码很简单。
注意同一数字是有多个，所以要对计数进行 -- ，减到 1 才再查下一个值，复杂度 O(n) ，实际的结果是 16 ms，还不错。

分治的关键是切分的方法。
起初以为是对半分成两个数组，然后走两数组中位数的路子，但那是两个已排序的数组，所以没法弄。
看了一些讲解，原来是利用quick sort的路数，选个pivot，大的扔左边，小的扔右边，扔完了就分好了。
然后看 k 在分割点（pivot）的哪边，在左边的话，说明 pivot 太小，比它大的不止 k 个，那就在左半边继续，
在右边的话，就说明 pivot 偏大，比它大的不够 k 个，所以在右边继续，但要扣掉左边已经找到的：k = (k - 左边)（含 pivot）。

实际写代码的时候，选 nums[k-1] 为 pivot，因为用的是双向扫描，且 pivot 换到头，而不是尾，所以搞得自己很晕。
双扫的时候，内外while 的条件都应该是 ii<=jj，必须要带等号，不然会出错（总感觉qs双扫 < 就够了···，再确认吧。）：
没有等号的话，无论是先 jj--，还是 ii++，后操作的会因为 ii<jj 而少移一步，到不了最终的位置 （ii –>右边起始，jj –>左边结束）。
挪完之后，并不需要把 pivot （最后一个大于 pivot 的数字）跟 ii-1 互换，因为要的不是排序，只是分割而已。
这样大于 pivot 的就从 start+1 开始，小于 pivot 的从 ii 开始，复杂度不算是O(lgn)，但比应该比 O(n) 小，跑出来是 4 ms！

好奇库函数的效果，所以又跑了一个 STL 的 sort，结果还不错呐，8 ms，库函数的 sort 好像是混合处理的？印象有点模糊了。
（Python的库函数跑出来是 40 ms 左右。）

以前面试的时候曾经遇到过基于这个题目的问题，
且 follow up 问的是如果这个数组会没完没了地增长，怎么能一直动态地输出的中位数？
从上面的解法来看，最好的选择应该是最小堆，新增一个，看是否大于堆顶，是的话替换并 reheapify。

bool mycmp(int a, int b){   return a>b; }
class Solution {
public:
    //---------------------------- Solution #1 : using quick sort, 4 ms ----------------------------
    int findKthLargest(vector<int>& nums, int k) {
        return qs(nums,0,nums.size()-1,k);
    }
    int qs(vector<int>& nums, int start, int end, int k)
    {
        swap(nums[start+k-1], nums[start]);
        int pv=nums[start];
        int ii=start+1, jj=end;
        while(ii<=jj)
        {
            while(ii<=jj && nums[ii]>=pv)       //keep bigger and equal numbers left
                ii++;
            while(jj>=ii && nums[jj]<pv)        //keep smaller numbers right
                jj--;
            if(ii<jj)
                swap(nums[ii], nums[jj]);
        }
        //swap(nums[--ii], nums[start]);        //we don't really have to switch pivot back
        if(k<ii-start)                          //more than k bigger number, go left
                                                //if swichted, use "k<ii-start+1" because of "--ii"
            return qs(nums, start+1, ii-1,k);   //if switched, range is "start" to "ii-1"
        else if(k>ii-start)                     //less than k; use "k<ii-start+1" if switched
            return qs(nums, ii, end, k-(ii-start)); //if switched, range is "ii+1" to end.
        else
            return pv;                          //exactly k bigger numbers, so pivot is the answer.
    }
    int swap(int& a, int& b)
    {
        int x=a;
        a=b, b=x;
    }
    /* 讨论区上的qs写法，每次选尾作为 pivot ，然后单向扫描把大的换到前面，代码简洁很多。导论上也是用的单扫。
    int quickSelect(vector<int>& nums, int start, int end, int k) {
        int pivot = nums[end], j = start;
        for (int i = start;i < end;++i)
            if (nums[i] > pivot)
                swap(nums[i],nums[j++]);
        swap(nums[j],nums[end]);                 //其实也不需要换了。
        if (k == j-start+1) return nums[j];
        if (k < j-start+1) return quickSelect(nums,start,j-1,k);
        else return quickSelect(nums,j+1,end,k-j+start-1);
    }
    */
    //---------------------------- Solution #2 : using map, 16 ms ----------------------------
    //use map to count all elements  then find the (nums.size()+1 -k)th smallest one.
    int findKthLargest_map(vector<int>& nums, int k) {
        map<int, int> buf;
        for(auto n : nums)
            buf[n]++;
       
        k=nums.size()+1-k;
        for(map<int, int>::iterator b=buf.begin(); b!=buf.end();)
        {
            if(1==(k--))
                return b->first;
            if(1<b->second)
                b->second--;
            else
                b++;
        }
        return 0;
    }
    //---------------------------- Solution #3 : using min-heap, 280 ms ----------------------------
    //put first k numbers into a min-heap,
    //check the rest, swap numbers bigger than root in heap and reheapify it
    int findKthLargest_minHeap(vector<int>& nums, int k) {
        int rst=0;
        int sz=nums.size();
        make_heap (nums.begin(),nums.begin()+k, mycmp);
        for(int ii=k; ii<sz; ++ii)
        {
            int tmp = nums[ii];
            if(tmp>nums[0])
            {
                nums[ii] = nums[0], nums[0]=tmp;
                make_heap (nums.begin(),nums.begin()+k, mycmp);
            }
        }
        rst=nums[0];
        return rst;
    }
    //---------------------------- Solution #4 : using max-heap, 1160 ms ----------------------------
    //put all numbers in a max-heap, pop first k-1 numbers
    int findKthLargest_maxHeap(vector<int>& nums, int k) {
        int rst=0;
        int sz=nums.size();
        while((k--))
        {
            make_heap (nums.begin(),nums.end());
            pop_heap (nums.begin(),nums.end());
            if(!k)
                rst=nums.back();
            nums.pop_back();      //试过不pop，计数扣掉所有pop的数字，耗时基本一样，看来主要耗时是 reheapify。
        }
        return rst;
    }

    //---------------------------- Solution #5 : using STL sort, 8 ms ----------------------------
    //sort, then find
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()-k];
    }
};
4 ms, 16 ms, 280 ms, 1160 ms, 8 ms.