TopK题-快速选择方法

代码

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）算法实现的时间复杂度：

1. 最好情况时间复杂度:

   • 当每次 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)。

2. 最坏情况时间复杂度 :

   • 当每次 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)。

3. 平均情况时间复杂度 :

   • 在平均情况下，我们可以期望 partition 操作能够将数组划分得比较均匀。虽然不一定是严格的一半，但 pivot 大概率不会总是落在极端位置。
   • 可以证明（通常使用期望分析），每次 partition 后，问题的规模平均会减少一个常数比例（例如期望减少到 3n/4 或 n/2 等）。
   • 类似于最好情况的分析，时间复杂度的递推关系大致可以认为是 T(n) <= O(n) + T(αn)，其中 α 是一个小于 1 的常数。
   • 解这个递推关系，可以得到 T(n) = O(n)。
   • 因此，平均情况时间复杂度为 O(n)。

总结：

• 最好情况: O(n)
• 最坏情况: O(n^2)
• 平均情况: O(n)

虽然最坏情况是 O(n^2)、但实际应用中、通过随机选择 pivot 或使用更健壮的 pivot 选择策略（如三数取中法）、可以大大降低遇到最坏情况的概率、使得算法的平均性能非常接近 O(n)。
我的代码使用了固定的 pivot（nums[left]）、

这里是引用

这使得它在面对特定输入（如已排序数组）时容易触发 O(n^2) 的最坏情况。