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

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

Учитывая массив 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. Теперь, чтобы решить эту проблему, выполните следующие шаги:

  1. Создайте набор S , в котором хранятся различные целые числа, присутствующие в массиве arr[] .
  2. Пройдите массив arr[] и вставьте каждое число в набор S .
  3. Верните минимум K и размер S , который является требуемым ответом.

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


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

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