Quick Select 快速选择

October 16, 2022 1283

开篇废话

最近有重要面试，时间真的很紧张啊！不会的还有好多，只能逐个快速击破了！QwQ

流程

  1. Choose a random pivot.
  2. Use a partition algorithm to place the pivot into its perfect position pos in the sorted array, move smaller elements to the left of pivot, and larger or equal ones - to the right.
  3. Compare pos and N - k to choose the side of array to proceed recursively.

模版

自用简易模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int findKthLargest(int[] nums, int k) {
  return quickSelect(nums, 0, nums.length - 1, k-1);
}

private int quickSelect(int[] nums, int l, int r, int k) {
  int index = partition(nums, l, r);
  if (index == k) return nums[k];
  return index < k ? quickSelect(nums, index+1, r, k) : quickSelect(nums, l, index - 1, k);
}

private int partition(int[] nums, int l, int r) {
  int pivot = nums[r];
  for (int i = l; i < r; i++) {
      if (nums[i] >= pivot) {
          swap(nums, l++, i);
      }
  }
  swap(nums, l, r);
  return l;
}

private void swap(int[] nums, int l, int r) {
  int tmp = nums[l];
  nums[l] = nums[r];
  nums[r] = tmp;
}

练习