快速选择算法

快速选择算法

题目描述：在未排序的数组中找到第 k 个最大的元素。

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

​ 快速选择算法本质上是对快速排序算法进行优化，快速排序算法是将数组进行划分，从数组中任选一个元素，调整数组使得左边元素都比它小，其4右侧元素都比它大。通过递归调用快速排序对左侧序列与右侧序列进行排序。而快速选择算法对左侧区间和右侧区间的数据个数与需要寻找的第K大的数字进行比较，选择答案所存在的区间，舍弃了另一个不需要的区间，使算法复杂度降低到$ O(n+ n/2 + n/4 +…)$期望为$O(n)$，但是在最坏的情况下每次选择的都是最大或者最小值，算法时间复杂度为$O(n^2)$。

针对题目数据，未加入随机数时间为56ms，加入随机数为16ms

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return quick_select(nums, 0, n - 1, n - k + 1);
    }
    
    int quick_select(vector<int>& nums, int l, int r, int k) {
        int randPos = l + rand() % (r - l + 1);
        swap(nums[l], nums[randPos]);
        int pivot = nums[l];
        int i = l, j = r;
        while (i < j) {
            while (i < j && nums[j] >= pivot) --j;
            if (i < j) nums[i] = nums[j];
            while (i < j && nums[i] < pivot) ++i;
            if (i < j) nums[j] = nums[i];
        }
        nums[i] = pivot;
        int idx = i - l + 1;
        if (idx == k) return pivot;
        else {
            return idx < k ? quick_select(nums, i + 1, r, k - idx) : quick_select(nums, l, i - 1, k);
        }
    }
};