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

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

Учитывая массив arr[] из N целых чисел, задача состоит в том, чтобы найти количество элементов в массиве, которые присутствуют K раз и их двойников нет в массиве.

Примеры:

Input: arr[] = {10, 6, 12, 8, 10, 8}, K = 2
Output: 2
Explanation: 10 is a valid number since it appears exactly two times and 20 does not appear in array.
8 is a valid number since it appears two times and 16 does not appear in array.

Input: arr[] = {1, 3, 5, 3}, K = 3
Output: 0
Explanation: No element in the given array satisfy the condition.

Input: arr[] = {1, 2, 2, 3, 3, 4}, K = 2
Output: 1
Explanation: Only 3 is valid element.
Though 2 is present twice but its double is also present.

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

  • Храните вхождения каждого из чисел в хэш-карту
  • Для каждого элемента, если частота равна K , проверьте, присутствует ли его двойник в хэш-карте или нет. Если он отсутствует, сохраните его как один из допустимых номеров.

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


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

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