/* * @param k : description of k * @param nums : array of nums * @return: description of return */ public int kthLargestElement(int k, int[] nums) { if (nums == null || nums.length == 0 || k <= 0) { return 0; } return quickSelect(nums, 0, nums.length - 1, nums.length - k + 1); } private int quickSelect(int[] nums, int left, int right, int k) { if (left == right) { return nums[left]; } int position = partition(nums, left, right); if (position + 1 == k) { return nums[position]; } else if (position + 1 < k) { return quickSelect(nums, position + 1, right, k); } else { return quickSelect(nums, left, position - 1, k); } } public int partition(int[] nums, int l, int r) { int left = l, right = r; int pivot = nums[left]; while (left < right) { while (left < right && nums[right] >= pivot) { right--; } nums[left] = nums[right]; while (left < right && nums[left] <= pivot) { left++; } nums[right] = nums[left]; } nums[left] = pivot; return left; }
Wednesday, August 17, 2016
Kth largest element
Same as find the kth smallest element: i.e., using quick select. Similar to quick sort, make sure that each time after the index method partition returns, the element at that index is the correct index when the array is sorted.
No comments:
Post a Comment