时间戳

首页 > 解决方案 > 数组中第 K 个最大的元素 - LeetCode 问题

java - 数组中第 K 个最大的元素 - LeetCode 问题

问题描述

我一直在尝试解决数组中的第 K 个最大元素

这是我的代码：

public static int findKthLargest(int[] nums, int k) {
       Queue<Integer> q = new LinkedList<>();
       int max = Integer.MIN_VALUE;

       for(int i=0; i< nums.length; i++){
           if(nums[i]>=max){
               max = nums[i];
               if(q.size() <k)
                   q.add(max);
               else{
                   q.poll();
                   q.add(max);
               }
           }
       }
       return q.peek();
   }

我的代码背后的主要思想是，我将最大值存储在长度为 K 的队列中，并且在遍历数组中的所有值之后，我返回第一个 Item，因为它是最大值 Kth 元素。

但它在以下测试用例中失败：输入：Array = [2, 1] K = 2 -- 预期输出：1 -- 我的输出：2

我只是不明白，1 怎么应该是数组中的第二大元素？如果我弄乱了任何东西，请纠正我。

标签： javaqueue

解决方案

我只是不明白，1 怎么应该是数组中的第二大元素？

如果数组只包含两个元素 -1和2，那么2是最大的，并且1是第二大的。它也是最小的，但这与问题无关。

你需要想出一个更好的解决问题的办法。当前算法仅在遇到新的“max”元素时才插入队列。但是如果你得到的第一个元素是最大的呢？您只会将其输入队列并错过所有其他人。

另外，为什么要使用队列？也许有序集合在这里会更有用？

推荐阅读