Длина наименьшего подмассива, в котором хотя бы один элемент повторяется K раз

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

Дан массив arr[] длины N и целое число K . Задача состоит в том, чтобы найти минимальную длину подмассива, чтобы хотя бы один элемент подмассива повторялся. ровно K раз в этом подмассиве. Если такого подмассива не существует, выведите -1 .

Примеры:

Input: arr[] = {1, 2, 1, 2, 1}, K = 2
Output: 3
Explanation:  Subarray [1,2,1], have K = 2 occurrences of 1

Input: arr[] = {2, 2, 2, 3, 4}, K = 3
Output: 3

Подход: обратите внимание, что в этой задаче наименьшая длина будет достигнута, когда у нас будет ровно один элемент в подмассиве с частотой K , что означает, что подмассив будет выглядеть примерно так [X . . . X] где X — элемент массива обр. Теперь выполните следующие действия, чтобы решить эту проблему:

  1. Создайте массив пар так, чтобы число (т.е. arr[i] ) было первым элементом, а его индекс (т.е. i ) вторым.
  2. Отсортируйте этот массив.
  3. Теперь создайте переменную mn для хранения ответа и инициализируйте ее значением INT_MAX .
  4. Теперь пройдите массив от i = 0 до i = (N – K) и на каждой итерации:
    • Если элемент в i и (i+K-1) равен, тогда сделайте mn равным минимуму из mn и разнице между индексами следующего.
  5. Верните mn в качестве окончательного ответа.

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

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

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