当前位置：首页 > backend >正文

TopK题-快速选择方法

backend 2025/5/6 5:34:56

在这里插入图片描述

代码

class Solution {public int findKthLargest(int[] nums, int k) {//k 就是对应的是下标 n - k 的位置 也就是说我们要的是下标n-k的元素return quickselect(nums, 0, nums.length - 1, nums.length - k);}public int quickselect(int[] nums, int left, int right, int k) {while (left <= right) {int pivotIndex = partition(nums, left, right);// 直接判断 pivotIndex 是否为我们需要的目标位置if (pivotIndex == k) {return nums[pivotIndex];} else if (pivotIndex < k) {// 在右边找left = pivotIndex + 1;} else {// 在左边找right = pivotIndex - 1;}}return -1; // 不可能触发}// 你指定不变的 partition 方法int partition(int[] nums, int left, int right) {int pivot = nums[left];int i = left + 1;int j = right;while (i <= j) {while (i <= right && nums[i] <= pivot) i++;while (j >= left + 1 && nums[j] > pivot) j--;if (i < j) {swap(nums, i, j);}}// 将 pivot 放到中间位置（即 j 处）swap(nums, left, j);return j;}void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

时间复杂度分析

好的，我们来分析一下你提供的快速选择（Quickselect）算法实现的时间复杂度：

最好情况时间复杂度:
- 当每次 partition 操作选取的 pivot 都恰好能将数组划分为两个大小相近的部分，并且我们要找的第 k 大元素总是位于较小的那个子数组中，或者 partition 操作第一次就找到了目标 pivotIndex == k。
- 在这种理想情况下，每次 partition 操作后，问题的规模大约减半。
- 第一次 partition 需要 O(n) 时间。
- 第二次大约需要 O(n/2) 时间。
- 第三次大约需要 O(n/4) 时间。
- …
- 总的时间复杂度是 T(n) = O(n) + O(n/2) + O(n/4) + … + O(1)。这是一个等比数列求和，收敛于 O(2n)。
- 因此，最好情况时间复杂度为 O(n)。
最坏情况时间复杂度 :
- 当每次 partition 操作选取的 pivot 都是当前子数组中的最小值或最大值时，并且我们要找的第 k 大元素总是位于那个包含剩下 n-1 个元素的较大子数组中。
- 例如，如果数组已经有序（或逆序）、并且每次都选择第一个元素作为 pivot。
- 第一次 partition 需要 O(n) 时间、问题规模变为 n-1。
- 第二次 partition 需要 O(n-1) 时间、问题规模变为 n-2。
- …
- 总的时间复杂度是 T(n) = O(n) + O(n-1) + O(n-2) + … + O(1)。这是一个等差数列求和。
- 因此，最坏情况时间复杂度为 O(n^2)。
平均情况时间复杂度 :
- 在平均情况下，我们可以期望 partition 操作能够将数组划分得比较均匀。虽然不一定是严格的一半，但 pivot 大概率不会总是落在极端位置。
- 可以证明（通常使用期望分析），每次 partition 后，问题的规模平均会减少一个常数比例（例如期望减少到 3n/4 或 n/2 等）。
- 类似于最好情况的分析，时间复杂度的递推关系大致可以认为是 T(n) <= O(n) + T(αn)，其中 α 是一个小于 1 的常数。
- 解这个递推关系，可以得到 T(n) = O(n)。
- 因此，平均情况时间复杂度为 O(n)。