Найдите N-е число в объединенных и отсортированных списках заданных диапазонов

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

Даны два целочисленных массива, L и R и целое число N . Каждый диапазон из данного массива обозначает, что присутствует каждое число в диапазоне [L[i], R[i]] . Задача состоит в том, чтобы вычислить N-й (индексация на основе 0) элемент, когда числа из заданных диапазонов упорядочены в порядке их сортировки .

Примеры :

Input: L = {1, 5}, R = {3, 7}, N = 4
Output: 6
Explanation: The numbers present are {1, 2, 3, 5, 6, 7}. Therefore 4-th element(0-indexed) is 6.

Input: L = {1, 3}, R = {4, 5}, N = 3
Output: 3
Explanation: The numbers present are {1, 2, 3, 4, 3, 4, 5} and their sorted order is {1, 2, 3, 3, 4, 4, 5}. Therefore 3-rd element(0-indexed) is 3.

Подход : Задачу можно решить с помощью бинарного поиска по ответу.
Выполните следующие шаги, чтобы решить проблему:

  • Вычислите две переменные min и max , которые хранят минимальный элемент из массива L и максимальный элемент из массива R.
  • Диапазон бинарного поиска будет [min, max] .
  • Для каждого mid = (min + max)/2 вычислить позицию текущего элемента.
  • Чтобы вычислить позицию, выполните итерацию по всем диапазонам и сделайте переменную t = 0 для хранения позиции . Проверьте два условия ниже, если L[i] >= mid
    • Если mid <= R[i] , обновить t += mid – L[i] + 1.
    • иначе t += R[i] – L[i] + 1
  • Диапазон бинарного поиска может быть обновлен как
    • если (t > n) макс = середина - 1.
    • иначе мин = середина + 1 .
  • Окончательный ответ будет храниться в переменной min .

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

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

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