import java.util.Random;
public class KthLargestElement {
public static int findKthLargest(int[] nums, int k) {
int n = nums.length;
int left = 0, right = n - 1;
Random rand = new Random();
while (left <= right) {
int pivotIndex = rand.nextInt(right - left + 1) + left;
pivotIndex = partition(nums, left, right, pivotIndex);
if (pivotIndex == n - k) {
return nums[pivotIndex];
} else if (pivotIndex > n - k) {
right = pivotIndex - 1;
} else {
left = pivotIndex + 1;
}
}
return -1;
}
private static int partition(int[] nums, int left, int right, int pivotIndex) {
int pivotValue = nums[pivotIndex];
swap(nums, pivotIndex, right);
int storeIndex = left;
for (int i = left; i <= right; i++) {
if (nums[i] < pivotValue) {
swap(nums, storeIndex, i);
storeIndex++;
}
}
swap(nums, storeIndex, right);
return storeIndex;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
int[] nums = {3, 2, 1, 5, 6, 4};
int k = 2;
int kthLargest = findKthLargest(nums, k);
System.out.println("第 " + k + " 大元素是:" + kthLargest);
}
}