Минимальное количество различных элементов, присутствующих в подпоследовательности длины K в массиве
Учитывая массив A[] , состоящий из N целых чисел и целого числа K , задача состоит в том, чтобы подсчитать минимальное количество различных элементов, присутствующих в подпоследовательности длины K данного массива, A .
Примеры:
Input: A = {3, 1, 3, 2, 3, 4, 5, 4}, K = 4
Output: 2
Explanation: The subsequence of length 4 containing minimum number of distinct elements is {3, 3, 3, 4}, consisting of 2 distinct elements, i.e. {3, 4}.Input: A = {3, 1, 3, 2, 3, 4, 5, 4}, K = 5
Output: 2
Explanation: The subsequence of length 5 containing minimum number of distinct elements is {3, 3, 3, 4, 4}, consisting of 2 distinct elements, i.e. {3, 4}.
Наивный подход: самый простой подход — сгенерировать все подпоследовательности длины K. и для каждой подпоследовательности найти количество присутствующих в них различных элементов. Наконец, выведите минимальное количество присутствующих различных элементов.
Временная сложность: O( K * NK)
Вспомогательное пространство: O(N)
Эффективный подход. Описанный выше подход можно оптимизировать с помощью хеширования . Выполните следующие шаги, чтобы решить проблему:
- Сохраните частоты всех элементов в данном массиве, A[] в HashMap, скажем, M .
- Пройдите по хэш-карте M и поместите частоты в другой массив, скажем, V .
- Отсортируйте массив Vin в порядке убывания.
- Инициализируйте две переменные, cnt и len равными 0, чтобы сохранить требуемый результат и длину сформированной таким образом подпоследовательности.
- Пройдите массив V[] с помощью переменной, скажем, i
- Если значение len ≥ K, то выйти из цикла.
- В противном случае увеличьте значение len на V[i] и cnt на 1 .
- После выполнения вышеуказанных шагов выведите в качестве результата значение cnt .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (N * log (N))
Вспомогательное пространство: O(N)