Максимизируйте количество различных элементов в подпоследовательности размера K в данном массиве
Учитывая массив arr[] из N целых чисел и целое число K , задача состоит в том, чтобы найти максимальное количество различных элементов во всех подпоследовательностях из K целых чисел.
Пример:
Input: arr[]={1, 1, 2, 2}, K=3
Output: 2
Explanation: The subsequence {1, 1, 2} has 3 integers and the number of distinct integers in it are 2 which is the maximum possible. Other possible subsequence is {1, 2, 2}.Input: arr[]={1, 2, 3, 4}, K=3
Output: 3
Подход: Данную проблему можно решить с помощью жадного подхода, используя наблюдение, что требуемый ответ является минимумом количества уникальных элементов в данном массиве или K. Теперь, чтобы решить эту проблему, выполните следующие шаги:
- Создайте набор S , в котором хранятся различные целые числа, присутствующие в массиве arr[] .
- Пройдите массив arr[] и вставьте каждое число в набор S .
- Верните минимум K и размер S , который является требуемым ответом.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(N)