LeetCode 精选 TOP 面试题：第K大元素快速选择算法

LeetCode 精选 TOP 面试题（5）215 数组中的第K个最大元素是一个经典的面试题，它采用了快速选择（Quick Select）的思路来解决。快速选择是在快速排序的基础上进行一半区间的递归，相比传统的排序算法，它可以更快地找到想要的元素。 其具体思路是，在特定区间 [l, r] 中选择一个数 x ，将大于等于 x 的放在左边，小于 x 的放在右边。其中[l, j] 是大于等于 x 的区间， [j+1, r] 是小于 x 的区间。然后判断第 k 大与 j 的大小关系，如果 k <= j ，则递归到 [l, j] 区间，否则递归到 [j+1, r]的区间。 需要注意的是，这里求的是第 k 大，而里面的方法 k 是指第 k 个位置，所以需要将 k 变成 k - 1 。 在时间复杂度分析上，虽然每层递归的时间复杂度为 O(n)，但并不是每次都会进入左右两部分的递归。仅进入一侧递归的情况下，数组长度会平均减半，因此时间复杂度为 O(n)。 下面是相应的 C++ 代码示例： ```cpp class Solution { public:      int findKthLargest(vector<int>& nums, int k) {        int left = 0, right = nums.size() - 1;        while (left <= right) {            int pivotIndex = partition(nums, left, right);            if (pivotIndex == k - 1) {                return nums[pivotIndex];            } else if (pivotIndex < k - 1) {                left = pivotIndex + 1;            } else {                right = pivotIndex - 1;            }        }        return -1;    }        int partition(vector<int>& nums, int left, int right) {        int pivot = nums[left];        int j = left;        for (int i = left + 1; i <= right; i++) {            if (nums[i] >= pivot) {                j++;                swap(nums[i], nums[j]);            }        }        swap(nums[left], nums[j]);        return j;    } }; ``` 通过上面的代码示例，我们可以看到快速选择的实现细节。首先是在 findKthLargest 函数中进行二分查找，然后在 partition 函数中进行数组的分区操作。这样可以很快地找到第 k 大的元素，并且在平均情况下时间复杂度为 O(n)。 总之，LeetCode 精选 TOP 面试题（5）215 数组中的第K个最大元素采用了快速选择的思路，在面试中是一个很好的思维训练和考察方式。