Randomized-Select

解决哪类问题

:::success 求解无序数组第K大/小元素（数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素） :::

代码模板

  1. class Solution {
  2.     public int findKthLargest(int[] nums, int k) {
  3.         return quickSort(nums, k, 0, nums.length - 1);
  4.     }
  5.     int quickSort(int[] nums,int k, int l, int r) {
  6.         if(l == r) return nums[l];
  7.         int left = l - 1, right = r + 1;
  8.         int mid = nums[l + r >> 1];
  9.         while(left < right){
  10.             while(nums[++left] > mid);
  11.             while(nums[--right] < mid);
  12.             if(left < right) swap(nums, left, right);
  13.         }
  14.         int number = right - l + 1;
  15.         if(number >= k) return quick_sort(nums, k, l, right);
  16.         return quickSort(nums, k - number, right + 1,r);
  17.     }
  18.     private void swap(int[] nums, int left, int right) {
  19.         int temp = nums[left];
  20.         nums[left] = nums[right];
  21.         nums[right] = temp;
  22.     }
  23. }

复杂度

平均时间复杂度：O(n)
最坏时间复杂度：O(n^2)

运用思想

递归

例题

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