215. Kth Largest Element in an Array

quickselect O(n) on avg

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        int n = nums.size(), l = 0, r = n - 1;
        while (l <= r) {
            int m = partition(nums, l, r);
            if (m == k - 1) return nums[m];
            if (m < k - 1) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }

    int partition(vector<int> &A, int l, int r) {
        vector<int> v{l, l + (r - l) / 2, r};
        swap(A[l], A[v[rand() % 3]]);
        int j = l + 1; // 从pivot下一个开始
        for (int i = j; i <= r; ++i) {
            if (A[i] > A[l]) {
                swap(A[i], A[j++]); // 凡是比pivot大的就往前换
            }
        }
        swap(A[--j], A[l]); // 拿最后一个比pivot大的跟pivot交换
        return j;
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand((unsigned)time(NULL));
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int i = partition(nums, l, r);
            if (i == k - 1) return nums[i];
            if (i > k - 1) {
                r = i - 1;
            } else {
                l = i + 1;
            }
        }
        return -1;
    }

    int partition(vector<int> &nums, int l, int r) {
        vector<int> v{l, (l + r) / 2, r};
        swap(nums[l], nums[v[rand() % 3]]);
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] <= pivot) { // 因为是求第k大所以要降序
                --r;
            }
            nums[l] = nums[r];
            while (l < r && nums[l] >= pivot) {
                ++l;
            }
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int l = 0, r = n - 1; // 左右闭区间
        while (l <= r) { // 要考虑l == r的情况
            auto i = partition(nums, l, r);
            if (i == k - 1) { // k是从1开始的
                return nums[i];
            } else if (i < k - 1) {
                l = i + 1;
            } else {
                r = i - 1;
            }
        }
    }

    int partition(vector<int> &nums, int left, int right) {
        int pivot = nums[left];
        int l = left, r = right;
        while (l < r) {
            while (l < r && nums[r] <= pivot) --r;
            nums[l] = nums[r];
            while (l < r && nums[l] >= pivot) ++l;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }
};

O(nlogk) 最小堆里永远保存k个数，堆顶的数是当前第k大的数，如果一个数比堆顶的数大，则入堆，堆自动调整后，将堆顶多余的第k+1大的数弹出

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> h;
        for (const auto &n : nums) {
            if (h.size() < k) {
                h.push(n);
            } else if (h.top() < n) {
                h.pop();
                h.push(n);
            }
        }
        return h.top();
    }
};