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

Опубликовано: 25 Февраля, 2023

Учитывая массив arr[] длины N , два массива start[] и end[] размера M каждый, где {start[i], end[i]} обозначает подмассив arr[] и целочисленное основание , задача определить максимальную высоту башни с заданным основанием , которую можно построить из элементов одного подмассива, ограниченного любым {start[i], end[i]} и удовлетворяющего следующим условиям:

  • Все элементы на каждом уровне должны быть равными.
  • Количество элементов на каждом уровне такое же, как и в базе .
  • Никакие два уровня не могут иметь один и тот же элемент.

Примеры:

Input: N = 9, arr[] = {1, 5, 7, 3, 2, 4, 6, 9, 8}, M = 3, start[] = {0, 3, 5}, end[] =  {8, 5, 6}, base = 1
Output: 9
Explanation: 
First Subarray = {0, 8}. There are 9 different elements. 
Each element can be kept in a different level.
So the height of the tower can be maximum 9 as base is 1. 
Second Subarray = {3, 5}. There are 3 unique elements.
So it will have height 3 at maximum.
Third Subarray = {5, 6}. We can form a tower of max height 2.
The maximum height among all the sub-arrays = 9.

Input: N = 5, arr[] = {1, 3, 3, 7, 5}, M = 2, start[] = {0, 1}, end[] =  {0, 3}, base = 2 
Output: 1
Explanation:
First Subarray = {0, 0}. height = 0 for this sub-array,  
because no tower of base 2 can be formed.
Second Sub-array = {1, 2}. Tower of height 1 can be formed by using 
arr[1] and arr[2] at 1st level of tower.
The maximum height of the tower that can be obtained from all the above subarrays is 1.

Подход: Чтобы решить проблему, следуйте следующей идее:

Count the frequency of each distinct element for each sub-array using Hash-Map. Initialized current_height a variable to zero, Traverse on Hash-Map and if an element’s frequency is greater than or equal to base then increment the current_height. Print the maximum value of Height H among all the sub-arrays.

Следуйте инструкциям, чтобы решить проблему:

  • Создайте переменную max_height и установите для нее значение max_height = 0 . Затем для каждого подмассива выполните следующие подшаги:
    • Создайте Hash-Map и current_variable = 0 .
    • Подсчитайте частоту каждого отдельного элемента и сохраните ее в Hash-Map как пару <элемент, частота>.
    • При перемещении по Hash-Map, если частота пары в Hash-Map больше или равна базе Tower, увеличьте current_height, а если current_height больше max_height , обновите max_height как current_height.
  • Выведите значение переменной max_height.

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

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

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