Вопрос:
Ссылка: https://leetcode.com/problems/top-k-frequent-elements/
Учитывая массив целых чисел nums
и целое число k
, вернуть наиболее часто встречающиеся элементы k
наиболее часто встречающиеся элементы. Вы можете вернуть ответ в любом порядке.
Пример 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Пример 2:
Input: nums = [1], k = 1 Output: [1]
Ограничения:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
k
находится в диапазоне[1, the number of unique elements in the array]
.- Гарантируется, что ответ уникальный.
Дополнительные сведения. Временная сложность вашего алгоритма должна быть меньше O(n log n)
, где n – размер массива.
Решение:
Подход:
- Метод
topKFrequent
принимает массив целых чиселnums
и целое числоk
в качестве входных данных и возвращает массив, содержащий K наиболее часто встречающихся элементов. - Он инициализирует целочисленный массив
res
длинойk
, в котором будет храниться результат. HashMap<Integer, Integer>
с именемtemp
создается для хранения частоты каждого элемента в массивеnums
.- Код перебирает каждый элемент
i
в массивеnums
и обновляет его частоту в картеtemp
. Еслиi
уже присутствует на карте, его частота увеличивается на 1. В противном случае он добавляется на карту с частотой 1. - После подсчета частот создается
PriorityQueue<Map.Entry<Integer, Integer>>
с именемsort
. В этой очереди приоритетов будут храниться записи карты, отсортированные по частоте их появления в порядке убывания. - Записи из карты
temp
добавляются в очередь с приоритетомsort
с помощью цикла for-each. - Затем код извлекает K самых частых элементов из приоритетной очереди, повторяя
k
раз. На каждой итерации он удаляет запись с наибольшей частотой из приоритетной очереди с помощью методаpoll()
и сохраняет ее ключ в массивеres
. - Наконец, в качестве результата возвращается массив
res
, содержащий K наиболее часто встречающихся элементов.
Код:
class Solution { public int[] topKFrequent(int[] nums, int k) { int[] res = new int[k]; Map<Integer, Integer> temp = new HashMap<>(); for(int i : nums){ if(temp.containsKey(i)){ temp.put(i, temp.get(i)+1); }else{ temp.put(i, 1); } } System.out.println(temp); PriorityQueue<Map.Entry<Integer, Integer>> sort = new PriorityQueue<>((a,b)->(b.getValue() - a.getValue())); for(Map.Entry<Integer, Integer> e : temp.entrySet()){ sort.add(e); } for(int i=0; i<k; i++){ Map.Entry<Integer, Integer> e = sort.poll(); res[i] = e.getKey(); } return res; } }
Временная сложность: O (N log k)
Космическая сложность: O(N)
Заключение:
Надеюсь, что этот блог поможет вам решить вопрос, а также развеет ваши сомнения относительно решения. Пожалуйста, прокомментируйте, если вы знаете какие-либо новые подходы. Если у вас есть какие-либо сомнения, пожалуйста, прокомментируйте, и мы обсудим их.
Удачного кодирования.