215. 數組中的第K大元素

思路

這個演算法衍生自三路快速排序。（應該說很像，兩者有沒有關聯我也不清楚。），目標是要找到第k大的數字。

演算法流程

第 k 大相當於第 n - k 小。

1. 陣列長度n，建立兩個變數left = 0，right = n - 1，代表搜索範圍。
2. 隨便選陣列中的一個數字x，利用三路快速排序步驟2, 3，找到=x的兩端位置smaller、greater。
3. 假如要找的位置在smaller、greater之間，表示這個數字即為所求。否則更新搜索範圍。

程式碼

1.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        auto partition = [&](int l, int r, int x) -> pair<int, int> { 
            int smaller = l, greater = r;
            int i = l;
            while(i <= greater) {
                if(nums[i] < x) {
                    swap(nums[smaller++], nums[i++]);
                }
                else if(nums[i] > x) {
                    swap(nums[greater--], nums[i]);
                }
                else {// nums[i] == x
                    i++;
                }
            }
            return {smaller, greater};
        };
        srand(time(nullptr));
        int n = nums.size();
        int left = 0, right = n - 1;
        k = n - k;
        while(true) {
            int x = nums[left + rand() % (right - left + 1)];
            auto mid = partition(left, right, x);
            if(k < mid.first) {
                right = mid.first - 1;
            }
            else if(k > mid.second) {
                left = mid.second + 1;
            }
            else {
                return x;
            }
        }
        return -1; // impossible
    }
};

複雜度分析

• 時間複雜度：$O(n)$，第一次劃分需要處理 $n$ 個元素，第二次 $n/2$ 個元素，
  以此類推 $O(n+\frac{n}2+\frac{n}4+\dots)=O(n)$
• 空間複雜度：$O(1)$，只有幾個變數存在。