leetcode 215. 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.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

题目大意：求一个未排序数组的第k大的数。

思路：

1、直接排序，时间复杂度：O(nlogn)

2、利用优先队列，维持一个大小为k的堆。时间复杂度：O(nlogk）

3、利用快排思想，时间复杂度：O(n)

C++代码：

class Solution {
    //划分函数，返回的数的索引值对应最终排序后的位置
    int partition(vector<int> &nums, int left, int right) {
        int p = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= p) right--;
            nums[left] = nums[right];
            while (left < right && nums[left] <= p) left++;
            nums[right] = nums[left];
        }
        nums[left] = p;
        return left;
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int p = partition(nums, l, r);
            if (p + k == nums.size())  { //满足这个条件表明p指向的位置是第k大的数
                return nums[p];
            }
            if (p + k < nums.size()) //这个时候只需要排序p后半部分的数组即可找到最终的第k大数
                l = p + 1;
            else //此时只需要排序p前半部分
                r = p - 1;
        }
        return nums[nums.size() - k];
    }
};