kth Largest Element

题目：

Find K-th largest element in an array.

Example: In array [9,3,2,4,8], the 3rd largest element is 4.

In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4, 3rd largest element is 3 and etc.

分析：

这道题有几种方法可以做

算法提高班内容，分析起来比较有意思，同时也参看九章的答案。
(1) 用O(nlogn)排序，返回第K个元素
(2) 用minHeap做O(n)的算法，但是空间复杂度是O(k)
(3) 用QuickSort思想做O(n)的算法，但是空间复杂度是O(1)

除此之外 在这个博客里面说了7种方法 http://www.cnblogs.com/zhjp11/archive/2010/02/26/1674227.html

1 我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。
2 利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)
3 利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
3.1 Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
3.2 Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)
4 二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)
5 用O(4*n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn)
6 维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)
7 利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

解法1：QuickSort

class Solution {
public:
    /*
     * param k : description of k
     * param nums : description of array and index 0 ~ n-1
     * return: description of return
     */
    int kthHelper(vector<int> nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        int i = left;
        int j = right;
        int pivot = nums[i + (j - i) / 2];
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            while (i <= j && nums[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(nums[i], nums[j]);
                i++;
                j--;
            }
        }

        if (left + k - 1 <= j) {
            return kthHelper(nums, left, j, k);
        }
        if (left + k - 1 < i) {
            return nums[left + k - 1];
        }
        return kthHelper(nums, i, right, k - (i - left));
    } 

    int kthLargestElement(int k, vector<int> nums) {
        // write your code here
        return kthHelper(nums, 0, nums.size() - 1, nums.size() - k + 1);
    }
};

解法2：minHeap

class Compare {
public:
    bool operator() (int lhs, int rhs) {
        return lhs > rhs;
    }
};

class Solution {
public:
    /*
     * param k : description of k
     * param nums : description of array and index 0 ~ n-1
     * return: description of return
     */
    int kthLargestElement(int k, vector<int> nums) {
        // write your code here
        if (nums.size() < k) {
            return -1;
        }
        priority_queue<int, vector<int>, Compare> mH;
        for (int i = 0; i < nums.size(); i++) {
            if (mH.size() < k) {
                mH.push(nums[i]);
            } else {
                int temp = mH.top();
                if (nums[i] > temp) {
                    mH.pop();
                    mH.push(nums[i]);
                }
            }
        }
        return mH.top();
    }
};