Создайте массив, состоящий из наиболее частых больших элементов, присутствующих в правой части каждого элемента массива.
Учитывая массив 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), так как мы используем дополнительное пространство для хранения сгенерированного массива.