[leetcode]215. Kth Largest Element in an Array 数组中第k大的元素

时间:2022-10-30 20:39:15

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

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

思路:

PriorityQueue

1. Have PriorityQueue created.
2. Insert all the elements into heap.
3. Call poll() k times.

代码:

 class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(); // default order: ((o1, o2) -> o1 - o2)
for(int n : nums) {
heap.add(n);
if (heap.size() > k) {
heap.poll();
}
} return heap.poll();
}
}

思路:

Quick Sort

核心思想是每次都要先找一个中枢点Pivot,然后遍历其他所有的数字,像这道题从小往大排的话,就把小于中枢点的数字放到左半边,把大于中枢点的放在右半边,这样中枢点是整个数组中第几大的数字就确定了,虽然左右两部分不一定是完全有序的,但是并不影响本题要求的结果,所以我们求出中枢点的位置,如果正好是k-1,那么直接返回该位置上的数字;如果大于k-1,说明要求的数字在左半部分,更新右边界,再求新的中枢点位置;反之则更新右半部分,求中枢点的位置