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

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

Учитывая массив A[] размера N , задача состоит в том, чтобы сгенерировать массив B[] на основе следующих условий:

  • Для каждого элемента массива A[i] найдите наиболее часто встречающийся элемент, больший, чем A[i] , присутствующий справа от A[i]. Вставьте этот элемент в B[] .
  • Если справа присутствует более одного такого элемента, выберите элемент с наименьшим значением.
  • Если справа от A[i] нет элемента большего, чем A[ i], затем вставьте -1 в B[] .

Наконец, выведите полученный массив B[] .

Примеры:

Input: A[] = {4, 5, 2, 25, 10, 5, 10, 3, 10, 5}
Output: 5, 10, 10, -1, -1, 10, -1, 5, -1, -1
Explanation:
A[0] (= 4): Array elements greater than 4 are {5, 25, 10}. Since 5 occurs maximum number of times, set B[0] = 5.
A[1] (= 5): Array elements greater than 5 are {25, 10}. Since 10 occurs maximum number of times, set B[1] = 10.
A[2] (= 2): Array elements greater than 2 are {5, 25, 10}. Since 10 occurs maximum number of times, set B[2] = 10.
A[3] (= 25): No element greater than A[3] found on its right. Therefore, set B[3] = -1.
A[4] (= 10): No element greater than A[4] found on its right. Therefore, set B[4] = -1.
Similarly, set B[5] = 10, B[6] = -1, B[7] = 5, B[8] = -1, B[9] = -1.
Therefore, the obtained array is B[] = {5, 10, 10, -1, -1, 10, -1, 5, -1, -1}.

Input: A[] = {1, 1, 3, 3, 2, 2}
Output: 2, 2, -1, -1, -1, -1

Наивный подход: выполните следующие шаги, чтобы решить проблему:

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

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

Временная сложность: O(N 2 ), так как мы используем вложенные циклы для обхода N*N раз.
Вспомогательное пространство: O(N), так как мы используем дополнительное пространство для хранения сгенерированного массива.

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