Найдите элементы, частота которых не менее чем в K раз превышает минимальную частоту.

Опубликовано: 26 Февраля, 2023

Для заданного массива A задача состоит в том, чтобы найти элементы, встречаемость которых не менее чем в K раз превышает частоту наименее встречающегося элемента в массиве.

Примеры:

Input: A = {4, 4, 3, 6, 6, 6, 8, 9}, K = 2
Output: {4, 6}
Explanation:  Frequency Table : {4:2, 3:1, 6:3, 8:1, 9:1},  
least occurring elements in nums are 8 and 9 with occurrence of 1. 
The elements required with 2 times of minimum occurrence i.e. 2 
are 4 and 6. As 4 is occurring 2 times and 6 is occurring 3 times.

Input: A = {3, 3}, K = 4
Output: {}

Подход: Идея такова, как указано ниже:

Store the frequency of each element and find the minimum frequency and then for each frequency check whether (K * min frequency) is less than or equal to the current frequency.

Выполните следующие шаги, чтобы решить проблему:

  • Сохраните все элементы массива в карте/хеш-таблице с их частотой
  • Перебрать элементы карты и найти минимальную частоту.
  • Теперь найдите элементы, которые встречаются более чем в K раз от этого минимального количества.

Ниже приведена реализация этого подхода:

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

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