快速选择

215. 数组中的第K个最大元素（Medium）

要找到第 k 个最大元素，实际就是找到数组中下标为 size - k 的元素。最容易想到的是排序，然后找到该下标的元素；或者使用大小为 k 的小顶堆，遍历数组后范围堆顶的值。

但是实际上可以利用快速排序的特点：一轮排序确定好的 pivot 的下标就是其在排好序后数组中的下标。

这样我们可以不用完整的排完序，只需要在 size - k 下标对应的元素确定时返回它即可。

以下代码采用的快排方法是 lomuto 快排

int quickSelect(vector<int>& nums, int bg, int ed, int targetInd)
{
    if (bg >= ed) return nums[bg];

    int randInd = bg + rand() % (ed - bg);
    int pivot = nums[randInd];
    swap(nums[bg], nums[randInd]);

    int left = bg;
    for (int i = bg + 1; i < ed; i++)
    {
        if (nums[i] < pivot)
            swap(nums[i], nums[++left]);
    }
    swap(nums[bg], nums[left]);
    // 找到目标下标，返回对应值
    if (left == targetInd)
		return nums[left];
	
    // 目标下标比当前确定的 pivot 下标大，说明在右区间
    if (left < targetInd)
        return quickSelect(nums, left+1, ed, targetInd);
    return quickSelect(nums, bg, left, targetInd);
}

int findKthLargest(vector<int>& nums, int k)
{
    return quickSelect(nums, 0, nums.size(), nums.size()-k);
}

这样时间复杂度可以做到 \(O(n)\)