public class Test68 {public static int findKthLargest(int[] nums, int k) {return randomizedSelcet(nums, nums.length - k);}public static int randomizedSelcet(int[] arr, int i) {int ans = 0;for (int l = 0, r = arr.length - 1 ; l <= r ; ) {partition(arr, l, r, arr[l + (int) (Math.random() * (r - l + 1))]);if (i < first) {r = first - 1;}else if(i > last) {l = last + 1;}else {ans = arr[i];break;}}return ans;}public static int first, last;public static void partition(int[] arr, int l, int r, int x) {first = l;last = r;int i = l;while (i <= last) {if (arr[i] == x) {i++;}else if (arr[i] < x) {swap(arr, first,i);first++;i++;}else{swap(arr ,i , last);last--;}}}public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;} }