Kth самый большой элемент в массиве - LeetCode Question

Question

Я пытался решить Kth наибольший элемент в массиве

Это мой код:

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.

Но он не работает в следующем тестовом примере: Input: Array = [2, 1] K = 2 - Ожидаемый результат: 1 - Мой вывод: 2

Я просто не понимаю, как 1 должен быть вторым по величине элементом вмассив? Пожалуйста, поправьте меня, если я что-то испорчу.

Answer 1

Я просто не понимаю, как 1 должен быть вторым по величине элементом в массиве?

Если массив состоит только из двух элементов - 1и 2, тогда 2 является самым большим, а 1 является вторым по величине. Он также самый маленький, но это не имеет отношения к вопросу.

Вам нужно подумать о лучшем решении проблемы. Текущий алгоритм вставляется в очередь только в том случае, если вы встретите новый элемент "max". Но что, если первый элемент, который вы получите, является самым большим? Вы бы только ввели его в очередь и пропустили все остальные.

Кроме того, зачем использовать очередь? Возможно, заказанная коллекция была бы более полезна здесь?