解题思路:
快速选择,目标是找出数组中第 k 小(或第 k 大)的元素,而不是对整个数组进行排序。
(需要和快排进行区分,快排的目的是排序)
注意:
i = l - 1, j = r + 1; 为什么要这么写?而不是 i = l; j = r ?
因为是先执行do语句的内容,一开始进循环就已经先i++或者j--了,所以进循环前需要-1和+1。
java">class Solution {public int findKthLargest(int[] nums, int k) {int n = nums.length;return quickselect(nums, 0, n - 1, n - k);}public int quickselect(int[] nums, int l, int r, int k) {if (l == r) return nums[k];int i = l - 1, j = r + 1;while (i < j) {do i++; while (nums[i] < nums[l]);do j--; while (nums[j] > nums[l]);if (i < j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}if (k <= j) return quickselect(nums, l, j, k);else return quickselect(nums, j + 1, r, k);}
}