K-й наименьший элемент в отсортированном массиве, сформированном путем реверсирования подмассивов из случайного индекса

Учитывая отсортированный массив arr[] размера N и целое число K , задача состоит в том, чтобы найти K ^-й наименьший элемент, присутствующий в массиве. Данный массив получен путем перестановки подмассивов {arr[0], arr[R]} и {arr[R + 1], arr[N – 1]} по некоторому случайному индексу R. Если ключ отсутствует в массиве массив, напечатать -1 .

Примеры:

Input: arr[] = { 4, 3, 2, 1, 8, 7, 6, 5 }, K = 2
Output: 2
Explanation: Sorted form of the array arr[] is { 1, 2, 3, 4, 5, 6, 7, 8 }. Therefore, the 2nd smallest element in the array arr[] is 2.

Input: arr[] = { 10, 8, 6, 5, 2, 1, 13, 12 }, K = 3
Output: 5

Наивный подход: самый простой подход к решению проблемы — отсортировать заданный массив arr[] в порядке возрастания и вывести K ^-й наименьший элемент в массиве.

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

Альтернативный подход к приведенному выше решению: мы можем отсортировать массив без использования какой-либо техники сортировки, что, несомненно, уменьшит временную сложность. Мы можем просто найти опорную точку P в массиве (вокруг которой происходит вращение) с помощью бинарного поиска и просто перевернуть два подмассива [0, P + 1] и [P + 1, N] с помощью функции std::reverse() в С++.

Реверсирование подмассивов: после нахождения точки поворота P просто найдите реверс двух подмассивов следующим образом:

std::reverse(обр, обр + P + 1);

std::reverse(обр + P + 1, обр + N);

Таким образом, мы получаем отсортированный массив и можем вывести K -й наименьший элемент как arr[K-1] .

Временная сложность: O(N)

Вспомогательное пространство: O(1)

Эффективный подход: оптимальная идея основана на наблюдении, что элемент R является наименьшим элементом, поскольку элементы в диапазоне [1, R] перевернуты. Теперь, если случайным индексом является R , это означает, что подмассив [1, R] и [R + 1, N] отсортированы в порядке убывания. Поэтому задача S сводится к нахождению значения R , которое можно получить с помощью бинарного поиска. Наконец, ^{выведите} K наименьший элемент.

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

• Инициализируйте l как 1 и h как N , чтобы сохранить индекс граничных элементов пространства поиска для бинарного поиска.
• Цикл, пока значение l+1 < h
  • Сохраните средний элемент в переменной mid как (l+h)/2 .
  • Если обр[л] ≥ обр[середина]. Если это правда, проверьте правую часть от mid , обновив l до mid .
  • В противном случае обновите r до mid .
• Теперь, после нахождения R , если K ≤ R , то ответ будет arr[R-K+1]. В противном случае arr[N-(KR)+1] .

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

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