class Solution {
private Random random = new Random();
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
private int quickSelect(int nums[], int left, int right, int index) {
int pivot = randomizedPartition(nums, left, right);
if (pivot < index) {
return quickSelect(nums, pivot + 1, right, index);
} else if (pivot > index) {
return quickSelect(nums, left, pivot - 1, index);
} else {
return nums[pivot];
}
}
private int randomizedPartition(int[] nums, int left, int right) {
int index = left + random.nextInt(right - left + 1);
swap(nums, index, right);
return partition(nums, left, right);
}
private int partition(int[] nums, int left, int right) {
int x = nums[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (nums[j] <= x) {
i++;
swap(nums, i, j);
}
}
swap(nums, i + 1, right);
return i + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
时间复杂度：
O
(
n
)
O(n)
O(n)。
空间复杂度：
O
(
O(
O(log
n
)
n)
n)，递归使用栈空间的空间代价的期望为
O
(
O(
O(log
n
)
n)
n) 。
相关题目