Максимальное количество уникальных элементов K, которые можно выбрать из массива.

Опубликовано: 21 Сентября, 2022

Даны массивы arr[] размера N и массив запросов Q[] размера M, где Q[i] определяет количество уникальных элементов, которые необходимо выбрать из массива arr[]. Задача найти максимальное количество элементов, которые можно выбрать для каждого запроса.

Примеры:

Input: arr[ ] = {30, 31, 32, 33, 32, 32, 31, 30, 30, 32}, Q[ ] = {1, 3}
Output: 4 9
Explanation: 
Frequency of 32 is 4, 30 is 3, 31 is 2 and 33 is 1.
For Q[0](=1), pick all 32. Hence count = 4.
For Q[1](=3), pick all 32, 30, and 31. Hence count = 4 + 3 + 2 = 9.

Input: arr[ ] = {22, 35, 22, 22, 35}, Q[ ] = {4, 5, 1}
Output: 5 5 3

Подход: Эту проблему можно решить, сохраняя частоты каждого элемента на карте. Выполните следующие шаги, чтобы решить эту проблему:

  • Инициализируйте структуру данных карты, скажем, Map и выполните итерацию по массиву arr[], затем сохраните частоту каждого элемента массива arr[] в Map.
  • Сохраните все значения Map в массиве, скажем, Cum_freq[], затем отсортируйте массивCum_freq[] в порядке убывания.
  • Выполните итерацию в диапазоне [1, размер Cum_freq[]] , используя переменную i , и обновите значение Cum_freq[i] + Cum_freq[i-1] в Cum_freq[i].
  • Итерация в диапазоне [0, размер запросов[]] с использованием переменной i:
    • Если запросы[i] >= размера Cum_freq[], то выведите N.
    • В противном случае выведите Cum_freq[queries[i] – 1].

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ