写一个方法返回一个整数数组中第k大的数 |21xrx.com

写一个方法返回一个整数数组中第k大的数

2023-06-17 16:59:19 深夜i -- --

Java 数据结构优先队列

如给定数组[3,2,1,5,6,4]，第3大的数为4。

如何编写一个方法来找到第k大的数？

在编写任何代码之前，我们需要仔细读问题并了解所需的输入和输出。从问题中我们得知：我们有一个整数数组和一个整数k，要求找到该数组中第k大的数。

那么如何开始编写代码？我们可以利用Java提供的现成的数据结构——优先队列（Priority Queue）。优先队列是具有特殊性质的队列，每次取出的元素都是队列中优先级最高的元素。

我们可以利用优先队列来找到第k大的数。优先队列中的元素在进入队列时会默认按照从小到大的顺序排列，所以我们可以通过修改比较函数来实现优先队列中元素的降序排列。我们可以在第一次遍历数组时将数组中的元素加入优先队列中，然后在第二次遍历时，依次弹出队列中的前k-1个元素，最后返回队列中的第一个元素即为第k大的数。

以下是代码实现：


import java.util.PriorityQueue;
public class KthLargestElementInArray {
  public int findKthLargest(int[] nums, int k) {
    PriorityQueue
  pq = new PriorityQueue<>((a, b) -> b - a); // 大的优先
 
    for (int num : nums) {
      pq.offer(num);
    }
    for (int i = 0; i < k - 1; i++) {
      pq.poll();
    }
    return pq.peek();
  }
  public static void main(String[] args) {
    KthLargestElementInArray kthLargestElementInArray = new KthLargestElementInArray();
    int[] nums = 1;
    int k = 3;
    System.out.println(kthLargestElementInArray.findKthLargest(nums, k)); // 输出4
  }
}

上一篇: idea打包java可执行jar包

下一篇: 学习C语言是否能成为一名电工

评论区

()

相似文章

写一个方法 返回一个整数数组中第k大的数

评论区

写一个方法返回一个整数数组中第k大的数