力扣 | 215. 数组中的第K个最大元素

2023-12-19 20:53:40
/* leetcode 347 号算法题:前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。

输入: nums = [1,1,1,2,2,3], k = 2
输出: [2, 1]

输入: nums = [1], k = 1
输出: [1]

1 <= nums.length <= 10^5
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的

进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。
 */

首先,我们来对比一下PriorityQueue的add()和offer()方法的主要区别: 方法 描述 抛出异常 返回特殊值
add() 向队列中添加元素 是 否 offer() 向队列中添加元素 否 是
从表格可以看出,add()方法方法则不会抛出异常在向队列中添加元素时,如果队列已满,则会抛出异常。而offer(),而是返回一个特殊值,通常是true或false,用于表示元素是否成功添加到队列中。因此,在使用过程中,我们需要根据具体需求选择使用哪个方法。

import java.util.PriorityQueue;

public class Problem_215_FindKthLargestNum {
    public int findKthLargestNum(int [] nums,int k){
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            pq.add(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if(nums[i] > pq.peek()){
                pq.remove();
                pq.add(nums[i]);
            }
        }
        return pq.remove();
    }
    //第二种方式!
    public int findKthLargestNum1(int [] nums,int k){
        PriorityQueue<Integer> pq = new PriorityQueue<>(k + 1);
        for (int i = 0; i < nums.length; i++) {
                pq.add(nums[i]);
                if(pq.size() > k){
                    pq.remove();
                }
        }
        return pq.remove();
    }

}

文章来源:https://blog.csdn.net/qq_37247026/article/details/135091779
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。