Найдите частоту каждого элемента в отсортированном массиве

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

Дан отсортированный массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти частоты каждого элемента массива.

Примеры:

Input: arr[] = {1, 1, 1, 2, 3, 3, 5, 5, 8, 8, 8, 9, 9, 10} 
Output: Frequency of 1 is: 3
              Frequency of 2 is: 1
              Frequency of 3 is: 2
              Frequency of 5 is: 2
              Frequency of 8 is: 3
              Frequency of 9 is: 2
              Frequency of 10 is: 1

Input: arr[] = {2, 2, 6, 6, 7, 7, 7, 11} 
Output:  Frequency of 2 is: 2
               Frequency of 6 is: 2
               Frequency of 7 is: 3
               Frequency of 11 is: 1

Наивный подход. Самый простой подход — пройтись по массиву и вести подсчет каждого элемента, встречающегося в HashMap, а затем, в конце концов, распечатать частоты каждого элемента путем обхода HashMap. Здесь этот подход уже реализован.

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

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

  • Инициализируйте переменную, скажем, freq как 1 , чтобы сохранить частоту элементов.
  • Выполните итерацию в диапазоне [1, N-1], используя переменную i , и выполните следующие шаги:
    • Если значение arr[i] равно arr[i-1] , увеличьте freq на 1 .
    • В противном случае выведите значение частоты arr[i-1], полученное в freq , а затем обновите freq до 1 .
  • Наконец, после вышеуказанного шага выведите частоту последнего отдельного элемента массива как freq .

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

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

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