K-й наименьший элемент в массиве, который содержит A[i] ровно B[i] раз

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

Примеры:

Input: K = 4, A[] = {1, 2, 3}, B[] = {1, 2, 3} 
Output: 3
Explanation:
The array obtained by taking A[0], B[0] (= 1) time, A[1], B[1] (= 2) times, A[2], B[2]( = 3)  times is {1, 2, 2, 3, 3, 3}. Therefore, the 4^th element of the array is 3.

Input: K = 4, A[] = {3, 4, 5}, B[] = {2, 1, 3} 
Output: 3
Explanation:The array formed is {3, 3, 4, 5, 5, 5}. Therefore, the 4^th element of the array i.e 5.

Наивный подход: самый простой подход — перебрать диапазон [0, N — 1] и поместить элемент с i ^-м индексом массива B[i] раз в новый массив. Наконец, выведите K ^-й элемент полученного массива после сортировки массива по возрастанию.

Временная сложность: O(N*log(N)), где N — количество элементов в новом массиве.
Вспомогательное пространство: O(N)

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

• Найдите максимальный элемент массива A[] и сохраните его в переменной, скажем, M .
• Инициализируйте массив, скажем, freq[] размером M + 1 с { 0 }, чтобы хранить частоту каждого элемента.
• Итерация в диапазоне [0, N-1] с использованием переменной i :
  • Добавьте B[i] в freq[A[i]].
• Инициализируйте переменную, скажем, sum как 0, чтобы сохранить сумму префикса до определенного индекса.
• Перебрать диапазон [0, N – 1] , используя переменную, скажем, i :
  • Добавьте freq[i] в сумму.
  • Если sum больше или равно K , вернуть i.
• Наконец, верните -1.

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

Временная сложность: O(N), где N — размер массивов A[] и B[].
Вспомогательное пространство: O(M), где M — максимальный элемент массива A[] .