leetcode-215-Kth-Largest-Element-in-an-Array

描述


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();
}
}

相关问题


题目来源