leetcode215数组中的第K个最大元素

发表于 | 分类于

题目

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例一：

1
2
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例二：

1
2
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

题解

方法一：采用快排的partition的思想，因为一趟partition可以确定一个数所在的位置，大于它的放左边，小于它的放右边。partition的过程返回一个确定的位置，然后对比和K的大小，如果小于K，则找前面的值，如果大于K找后面的值。

方法二：采用优先级队列，使用一个最小堆，然后使用java的priorityqueue来实现。

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.PriorityQueue;

/**
 * 数组中的第K个最大元素
 */
public class leetcode215 {
    public int findKthLargest(int[] nums, int k) {
        if (nums==null||nums.length==0)return 0;
        int left =0;
        int right = nums.length-1;
        while (true){
            int pos =partition(nums,left,right);
            if (pos+1==k){
                return nums[pos];
            }else if (pos+1>k){
                right=pos-1;
            }else {
                left=pos+1;
            }
        }
    }
    private int partition(int[] nums,int left,int right){
        int pivot = nums[left];
        int l = left+1;
        int r =right;
        while (l<=r){
            if (nums[l]<pivot&&nums[r]>pivot){
                swap(nums,l,r);
            }
            if (nums[l]>=pivot)l++;
            if (nums[r]<=pivot)r--;
        }
        swap(nums,left,r);
        return r;
    }
    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;

    }

    public int findKthLargest2(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();//删除头部元素
            }
        }
        return minHeap.poll();
    }
}