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