Вопрос:

Ссылка: 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 – размер массива.

Решение:

Подход:

  1. Метод topKFrequent принимает массив целых чисел nums и целое число k в качестве входных данных и возвращает массив, содержащий K наиболее часто встречающихся элементов.
  2. Он инициализирует целочисленный массив res длиной k, в котором будет храниться результат.
  3. HashMap<Integer, Integer> с именем temp создается для хранения частоты каждого элемента в массиве nums.
  4. Код перебирает каждый элемент i в массиве nums и обновляет его частоту в карте temp. Если i уже присутствует на карте, его частота увеличивается на 1. В противном случае он добавляется на карту с частотой 1.
  5. После подсчета частот создается PriorityQueue<Map.Entry<Integer, Integer>> с именем sort. В этой очереди приоритетов будут храниться записи карты, отсортированные по частоте их появления в порядке убывания.
  6. Записи из карты temp добавляются в очередь с приоритетом sort с помощью цикла for-each.
  7. Затем код извлекает K самых частых элементов из приоритетной очереди, повторяя k раз. На каждой итерации он удаляет запись с наибольшей частотой из приоритетной очереди с помощью метода poll() и сохраняет ее ключ в массиве res.
  8. Наконец, в качестве результата возвращается массив 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)

Заключение:

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

Удачного кодирования.