Длина наименьшего подмассива, состоящего из всех вхождений всех максимально встречающихся элементов

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

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

Input: arr[] = {1, 2, 1, 3, 2}
Output: 5
Explanation: Elements with maximum frequency (=2) are 1 & 2. 
Therefore, the length of smallest subarray consisting of all the occurrences of 1 and 2 is 5 i.e {1, 2, 1, 3, 2}

Input: arr[] = {1, 2, 5, 1, 5, 5}
Output: 4

Подход: задачу можно решить, отслеживая первые и последние вхождения максимально встречающихся элементов. Длина наименьшего подмассива будет разницей между максимумом последних вхождений и минимумом первых вхождений.
Выполните следующие шаги, чтобы решить проблему:

  • Создайте карту для хранения частот элементов
  • Найдите элементы с максимальной частотой и сохраните их первое и последнее вхождение.
  • Наконец, верните разницу между максимумом последних вхождений и минимумом первых вхождений.

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


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

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