NC88 寻找第K大

题目链接：https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf

题目描述

有一个整数数组，请你根据快速排序的思路(不一定比Arrays.sort()的性能好！)，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

要求：时间复杂度 O(nlogn)，空间复杂度 O(1)

数据范围：0≤n≤10^5， 1≤K≤n，数组中每个元素满足 0≤val≤10^9

示例 1：

输入：[1,3,5,2,2],5,3
返回值：2

示例 2：

输入：[10,10,9,9,8,7,5,6,4,3,4,2],12,3
返回值：9
说明：去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9

解题代码

方法一(截图)：
import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        Arrays.sort(a);
        return a[n - K];
    }
}

方法二：
import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        PriorityQueue<Integer> queue = new PriorityQueue<>((n1, n2) -> n2 - n1);
        while (n-- > 0) {
            queue.add(a[n]);
        }
        while (--K > 0) {
            queue.poll();
        }
        return queue.peek();
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2022/07/12 09:51:23