215.Kth Largest Element in an Array

Tags: Heap Linked List Medium

Links: https://leetcode.com/problems/kth-largest-element-in-an-array/

---

Find the **k**th 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.

---

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for (auto e : nums) pq.push(e);

        int res = 0;
        while (k--) {
            res = pq.top();
            pq.pop();
        }

        return res;
    }
};

此题目的本意不是考最大堆，应该尽可能的考虑用分治法来求解。

但是很显然分治法的时间性能并不是很好。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        return solve(0, nums.size() - 1, nums, k);
    }

    int solve(int left, int right, vector<int> & nums, int k)
    {
        if (left == right) return nums[left];

        int pivot = nums[left];
        int start = left, end = right;
        while (start < end) {
            while (start < end && nums[end] < pivot) --end;
            if (start < end) nums[start++] = nums[end];

            while (start < end && nums[start] >= pivot) ++start;
            if (start < end) nums[end--] = nums[start];
        }

        if (start + 1 == k) return pivot;
        else if (start + 1 < k)
            return solve(start + 1, right, nums, k);
        else
            return solve(left, start - 1, nums, k);  
    }
};

相当于是快速排序的变形，时间复杂度为$O(n)$，因为每次平均下来相当于折半，则$O(n + n/2 + n/4+\cdots +1)=O(n)$。

思路是选择pivot，左端为大端降序排列。