NowCoder088–寻找第k大

题目描述

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

示例1

输入
[1,3,5,2,2],5,3

返回值

2

代码:

package com.xujinshan.nowcoder.nc088;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author: xujinshan361@163.com
 * NowCoder088--寻找第K大
 * 题目描述
 * <p>
 * 有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
 * <p>
 * 给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。
 * 示例1
 * 输入
 * <p>
 * [1,3,5,2,2],5,3
 * <p>
 * 返回值
 * <p>
 * 2
 */

/**
 * 直接调用java函数，可以通过测试
 */
class Solution01 {
    public int findKth(int[] a, int n, int K) {
        Arrays.sort(a);
        return a[n - K];
    }
}

class Solution02 {
    public int findKth(int[] a, int n, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i : a) {
            pq.add(i);
            if (pq.size() > K) {        // 堆的大小保持为k
                pq.poll();      // 如果比k大，则把k+1个元素中的最小的poll出来
                // 让剩下的元素以小根堆的形式重新排列
            }
        }
        return pq.peek();
    }
}

public class NowCoder088 {
    public static void main(String[] args) {
        System.out.println(new Solution02().findKth(new int[]{1, 3, 5, 2, 2}, 5, 3));
    }
}

结果：