描述
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:
1 2
| Input: [3,2,1,5,6,4] and k = 2 Output: 5
|
Example 2:
1 2
| Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4
|
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
分析
和 Kth Smallest Element in a Sorted Matrix 这道题类似,可以用优先队列解决,不过那道题用的是最大堆,这道题用的是最小堆,在堆顶的是整个数组中由大到小排列的第 k 个数,它的 k-1 个子节点都比它大。
解决方案1(Python)
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
| class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: numsLen = len(nums) self.buildMaxHeap(nums) for i in range(k-1): nums[0], nums[numsLen-1-i] = nums[numsLen-1-i], nums[0] self.adjust(nums, 0, numsLen-1-i-1) return nums[0] def buildMaxHeap(self, nums): numsLen = len(nums) for root in range(numsLen//2, -1, -1): self.adjust(nums, root, numsLen-1) def adjust(self, nums, root, high): if root > high: return originRootValue = nums[root] child = 2*root + 1 while child <= high: if child+1 <= high and nums[child] < nums[child+1]: child += 1 if originRootValue >= nums[child]: break nums[root] = nums[child] root = child child = 2 * root + 1 nums[root] = originRootValue
|
解决方案1(Java)
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(k); for (int i = 0; i < nums.length; i++) { heap.add(nums[i]); if (heap.size() > k) { heap.poll(); } } return heap.peek(); } }
|
相关问题