题目描述

原题链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

解题思路：快速选择

官方题解的文字说明挺好的，可以去看看：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/

快速选择和快速排序一样，都是要写个方法，然后该方法再调用切分方法！

8.10 心得：

最大的第 K 个元素 = 从小到大排序的倒数第 K 个元素 = 数组下标为 nums.length - k

看官方题解文字说明得出得心得：
- 快速排序是切分后的左右两区间都得递归的去排序，而快速选择不用切分后都去递归左右两区间，只需判断我们需要找的数据下标在哪个区间然后去递归那一边的区间就行了。
- 并且也不用递归到全部元素有序，只需要得到我们想要的元素的下标位置确定了即可，该位置的元素就是我们想要的，此时的状态是该元素左侧的元素都比它小但不是元素的，右侧的元素都比它大并且也不是有序的，左右两侧都不是有序的也没关系，我们不用继续递归的去排成有序的，只需要返回我们需要的下标的元素即可，可以肯定该元素在原数组中一定是有序的！
所以，快排的时间复杂度是 O(Nlogn) 而快速选择的时间复杂度是 O(N)，为啥是 O(N) 原因在上面。

9.14 心得：

下面第 7 行代码和快排不同，就随便瞎试，对了就行

class Solution {
  public int findKthLargest(int[] nums, int k) {
      return quickSelect(nums, 0, nums.length - 1, nums.length - k);
  }
  public int quickSelect(int[] nums, int l, int r, int k) {
      if(l > r) return 0;
      int OkSortIndex = partition(nums, l, r);
      if(k == OkSortIndex) return nums[OkSortIndex];
      else if(k < OkSortIndex) return quickSelect(nums, l, OkSortIndex - 1, k);
      else return quickSelect(nums, OkSortIndex + 1, r, k);
  }
  public int partition(int[] nums, int l, int r) {
      // 比如:new Random().nextInt(100) 的取值范围是 [0, 100)
      swap(nums, l, new Random().nextInt(r - l + 1) + l); // 随机化，防止最坏情况
      int cut = nums[l];
      int i = l, j = r;
      while(i < j) {
          while(i < j && nums[j] >= cut) j--;
          while(i < j && nums[i] <= cut) i++;
          if(i < j) swap(nums, i, j);
      }
      swap(nums, l, j);
      return j;
  }
  public void swap(int[] nums, int i, int j) {
      int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
  }
}

数据结构与算法

3. 数组中的第 K 个最大元素

题目描述

解题思路：快速选择