Problem
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. k is always valid, 1 ≤ k ≤ array's length.
Example
given [3,2,1,5,6,4] and k = 2, return 5.
JavaScript Code
function findKthLargest(nums, k) { if (k < 1 || nums == null) { return 0; } return getKth(nums.length - k +1, nums, 0, nums.length - 1); } function getKth(k, nums, start, end) { var pivot = nums[end]; var left = start; var right = end; while (true) { while (nums[left] < pivot && left < right) { left++; } while (nums[right] >= pivot && right > left) { right--; } if (left == right) { break; } swap(nums, left, right); } swap(nums, left, end); if (k == left + 1) { return pivot; } else if (k < left + 1) { return getKth(k, nums, start, left - 1); } else { return getKth(k, nums, left + 1, end); } } function swap(nums, n1, n2) { var tmp = nums[n1]; nums[n1] = nums[n2]; nums[n2] = tmp; } console.log(findKthLargest([1,2,5,3,7,4],2));
This comment has been removed by the author.
ReplyDelete