Question
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| public int findKthLargest(int[] nums, int k) { if (nums == null || nums.length == 0) { return -1; } if (k <= 0 || k > nums.length) { return -1; } int res = partition(nums, 0, nums.length-1, k-1); for (int n : nums) { System.out.print(n+" "); } return res; }
public int partition(int[] nums, int start, int end, int k) { if (start >= end) { return nums[k]; } int left = start, right = end; int pivot = nums[start+(end-start)/2]; while (left <= right) { while (left <= right && nums[left] > pivot) { left++; } while (left <= right && nums[right] < pivot) { right--; } if (left <= right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } if (k <= right) { return partition(nums, start, right, k); } if (k >= left) { return partition(nums, left, end, k); } return nums[k]; }
|