Найдите элементы, частота которых не менее чем в K раз превышает минимальную частоту.
Для заданного массива 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)