215. Kth Largest Element in an Array215. 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.215. Kth Largest Element in an Array

---

本题要求一个未排序数组中第k大的数。
解法1，直接从大到小排序，然后取第k个数，时间复杂度O(nlgn)。

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

本代码提交AC，用时16MS。
解法2，借助快排的思路，每次选择一个枢纽pivot，把区间[left,right]划分为比pivot大和小的两个部分，然后就能确定pivot的最终位置，如果其下标正好是k-1，则说明pivot就是第k大的数。否则可以判断第k大的数在左半边还是右半边，然后递归在其中一半查找第k大的数。时间复杂度可以由T(n)=T(n/2)+O(n)解出是O(n)，注意我们只需要在其中一半递归，所以是加一个T(n/2)。
代码如下：

class Solution {
private:
    int helper(vector<int>& nums, int left, int right, int k)
    {
        if (left == right)
            return nums[left];
        int pivot = nums[left];
        int l = left, r = right;
        while (l < r) {
            while (l < r && nums[r] <= pivot)
                –r;
            if (l >= r)
                break;
            nums[l] = nums[r];
            while (l < r && nums[l] >= pivot)
                ++l;
            if (l >= r)
                break;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        if (l + 1 == k)
            return pivot;
        if (k < l + 1)
            return helper(nums, left, l – 1, k);
        else
            return helper(nums, l + 1, right, k);
    }
public:
    int findKthLargest(vector<int>& nums, int k) { return helper(nums, 0, nums.size() – 1, k); }
};

本代码提交AC，用时39MS，居然比直接排序还慢。。。
解法3，使用堆排序。对原数组建一个最大堆，然后不断的把前k-1个堆顶弹出，下一个堆顶元素就是第k大的元素。建堆时间为O(n)，维护堆的性质需要O(lgn)时间，所以总时间复杂度为O(klgn+n)。
代码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        priority_queue<int> pq(nums.begin(), nums.end());
        for (int i = 0; i < k – 1; ++i)
            pq.pop();
        return pq.top();
    }
};

本代码提交AC，用时9MS，是最快的。
二刷。还是使用快排划分的方法，但是这次把partition的过程单独抽出来了，逻辑更清晰，代码如下：

class Solution {
private:
    int partition(vector<int>& nums, int start, int end)
    {
        if (start >= end)
            return start;
        int i = start, j = end, pivot = nums[start];
        while (i < j) {
            while (i < j && nums[j] <= pivot)
                –j; // 注意符号，从大到小排序
            if (i < j) {
                nums[i] = nums[j];
                ++i;
            }
            while (i < j && nums[i] > pivot)
                ++i; // 注意符号，从大到小排序
            if (i < j) {
                nums[j] = nums[i];
                –j;
            }
        }
        nums[i] = pivot;
        return i;
    }
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        int start = 0, end = nums.size() – 1;
        while (true) {
            int p = partition(nums, start, end);
            if (p + 1 == k)
                return nums[p];
            else if (p + 1 < k)
                start = p + 1;
            else
                end = p – 1;
        }
        return -1;
    }
};

本代码提交AC，用时23MS。

三刷。更简洁不易出错的快排划分方法：

class Solution {
private:
	int FindK(vector<int>& nums, int left, int right, int k) {
		int pivot = nums[right];
		int next_idx = left;
		for (int i = left; i <= right; ++i) {
			if (nums[i] > pivot) {
				swap(nums[i], nums[next_idx++]);
			}
		}
		swap(nums[right], nums[next_idx]);
		int rank = next_idx + 1 - left;
		if (rank == k)return pivot;
		else if (k < rank)return FindK(nums, left, next_idx - 1, k);
		else return FindK(nums, next_idx + 1, right, k - rank);
	}
public:
	int findKthLargest(vector<int>& nums, int k) {
		return FindK(nums, 0, nums.size() - 1, k);
	}
};

本代码提交AC，用时212MS。