以i - 1为分界点
i - 1左边都是大于等于x
i右边都是小于等于x
并且x不能选择nums[l] 或者nums[l + r >> 1] 因为可能出在递归时出现死循环top(nums, l, r, k)
class Solution {
public int findKthLargest(int[] nums, int k) {
return topK(nums, 0, nums.length - 1, k);
}
private int topK(int[] nums, int l, int r, int k) {
if (l >= r) {
return nums[l];
}
int i = l - 1, j = r + 1;
int x = nums[l + r + 1 >> 1];
while (i < j) {
do {i++;} while (nums[i] > x);
do {j--;} while (nums[j] < x);
if (i < j) {
swap(nums, i, j);
}
}
if (i - 1 - l + 1 >= k) {
return topK(nums, l, i - 1, k);
} else {
return topK(nums, i, r, k - (i - 1 - l + 1));
}
}
private void swap(int[] nums, int l, int r) {
int t = nums[l];
nums[l] = nums[r];
nums[r] = t;
}
}
以j为分界点
j左边都大于等于x
j + 1右边都小于等于x
并且x不能选择nums[r] 或者nums[l + r + 1 >> 1] 因为可能出在递归时出现死循环top(nums, l, r, k)
class Solution {
public int findKthLargest(int[] nums, int k) {
return topK(nums, 0, nums.length - 1, k);
}
private int topK(int[] nums, int l, int r, int k) {
if (l >= r) {
return nums[l];
}
int i = l - 1, j = r + 1;
int x = nums[l + r >> 1];
while (i < j) {
do {i++;} while (nums[i] > x);
do {j--;} while (nums[j] < x);
if (i < j) {
swap(nums, i, j);
}
}
if (j - l >= k) {
return topK(nums, l, j, k);
} else {
return topK(nums, j + 1, r, k - (j - l + 1));
}
}
private void swap(int[] nums, int l, int r) {
int t = nums[l];
nums[l] = nums[r];
nums[r] = t;
}
}