Find Minimum in Rotated Sorted Array

Q: Какова временная сложность поиска минимального элемента в повернутом отсортированном массиве?

Время O(log n) и дополнительная память O(1) при бинарном поиске. На каждом шаге остаётся половина диапазона, поэтому для списка из 5000 элементов требуется не более 13 сравнений. Поиск точки разрыва выполняется за O(n) : он считывает каждый элемент, если минимум находится в конце.

Q: Почему сравнивать nums[mid] с nums[hi], а не с nums[lo]?

Потому что nums[hi] всегда позволяет определить, с какой стороны находится минимум, а nums[lo] — нет. Если nums[mid] > nums[hi] , значения должны находиться между mid и hi ; в противном случае nums[mid..hi] возрастает, и минимум находится в mid или до него. В случае с nums[lo] результат nums[mid] > nums[lo] подходит и для невращённого списка, где минимум — это nums[lo] , и для вращённого, где он находится правее mid .

Q: Как определить, сколько раз был повернут отсортированный массив?

Выполни тот же двоичный поиск и верни lo — индекс минимального элемента, а не nums[lo] . Если считать поворот перемещением последнего элемента в начало, этот индекс и будет количеством поворотов. Если считать его перемещением первого элемента в конец, как в этой задаче, количество равно (n - lo) mod n : в [11, 13, 15, 17, 2, 5, 9] минимальный элемент находится по индексу 4, а 7 минус 4 даёт 3 перемещённых значения.

Q: Работает ли бинарный поиск, если в массиве есть дубликаты?

Не остаётся неизменным. В [2, 2, 2, 0, 2] nums[mid] может быть равно nums[hi] , и тогда нельзя исключить ни одну из сторон. В этом случае безопасно сужать диапазон с помощью hi = hi - 1 , поскольку копия nums[hi] остаётся в диапазоне на позиции mid , но поиск в списке из одинаковых значений, среди которых скрыто одно меньшее значение, тогда занимает O(n) .

СреднеБинарный поиск

+10

Список различных целых чисел был отсортирован по возрастанию, а затем циклически сдвинут: некоторое количество элементов, возможно, ноль, взяли из начала и переместили в конец в том же порядке. Например, после циклического сдвига [2, 5, 9, 11, 13, 15, 17] на 3 позиции получится [11, 13, 15, 17, 2, 5, 9]. Тебе дан циклически сдвинутый список nums. Верни его наименьшее значение за время O(log n).

Функция

findMin(nums: integer-array) → integer

numsinteger-array: повёрнутый отсортированный список различных целых чисел
Возвращаетinteger: наименьшее значение в nums

Ограничения

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Все значения в nums различны.
nums — это возрастающий список, повернутый на некоторое k, где 0 ≤ k < nums.length; k = 0 оставляет его неповернутым.

Примеры

Ввод: nums = [11, 13, 15, 17, 2, 5, 9]
Вывод: 2
Пояснение: Значения возрастают от 11 до 17, а затем падают до 2, где начинается второй участок. При поиске обнаруживается, что 17 > 9 по индексу 3, поэтому минимум находится справа от него; затем 5 ≤ 9 и 2 ≤ 5 сдвигают hi назад, пока в диапазоне не останется только индекс 4, которому соответствует 2.

Ввод: nums = [4, 7, 10, 12]
Вывод: 4
Пояснение: Этот список был повернут на 0, поэтому он по-прежнему отсортирован, и минимальное значение — его первый элемент. Каждое среднее значение не больше последнего, поэтому hi продолжает перемещаться влево, пока не достигнет индекса 0, в котором находится 4.

Ввод: nums = [30, -6, 0, 8, 19]
Вывод: -6
Пояснение: Четыре значения переместились из начала в конец, поэтому наибольшее значение, 30, теперь стоит первым, а минимальное, -6, находится по индексу 1. Поиск сужает диапазон до индексов 0 и 1, видит, что 30 > -6, и перемещает lo на 1.

+17 скрытых тестов при отправке

Дополнительный вопрос

Можешь найти k-е наименьшее значение в nums за время O(log n), не сортируя массив?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Повернутый отсортированный список состоит из двух возрастающих последовательностей: [11, 13, 15, 17], а затем [2, 5, 9]. Минимум — это первое значение второй последовательности, сразу после единственного места, где значения убывают. Проход по списку находит это снижение за O(n). Сравнение значения в середине с последним значением диапазона показывает, по какую сторону от снижения находится середина, поэтому бинарный поиск находит его за O(log n).

Идите, пока значения не уменьшатся

Идея

В отсортированном списке каждое значение больше предыдущего. При циклическом сдвиге обе последовательности остаются отсортированными, и появляется ровно одно место, где это правило нарушается: за наибольшим значением следует наименьшее. Поэтому пройдите список слева направо и верните первое значение, которое меньше своего левого соседа. Если такого значения нет, список был сдвинут на 0 позиций, а минимум — это nums[0].

В списке [11, 13, 15, 17, 2, 5, 9] проход встречает 13, 15 и 17 — каждое из них больше предыдущего значения — и останавливается на индексе 4, где 2 меньше 17. Это уже лучше, чем искать минимум среди всех значений, поскольку проход останавливается на спаде, но спад может находиться где угодно. Если при сдвиге переместился один элемент, как в [2, 3, 4, 5, 6, 7, 8, 1], проход проверит весь список: 5000 сравнений для 5000 элементов, тогда как бинарному поиску требуется 13.

Алгоритм

Для каждого индекса i от 1 до n-1 сравните nums[i] с nums[i-1].
Если nums[i] < nums[i-1], верните nums[i]: там начинается второй проход.
Если цикл завершится, список не был циклически сдвинут: верните nums[0].

def findMin(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            return nums[i]  # the only drop: the second run starts here
    return nums[0]  # no drop: the list was not rotated

Двоичный поиск по последнему значению

Идея

Соблюдайте одно обещание: минимум находится между lo и hi включительно. В начале этот диапазон охватывает весь список. Посмотрите на среднее значение и сравните его с nums[hi] — последним значением диапазона.

Если nums[mid] > nums[hi], где-то между mid и hi значения убывают, и минимум — это значение сразу после этого спада, то есть оно находится правее mid: установите lo = mid + 1. В противном случае nums[mid] < nums[hi] (все значения различны), поэтому на отрезке nums[mid..hi] значения возрастают и нет спада. Значит, минимум — это nums[mid] или какое-то значение перед ним, поэтому установите hi = mid. Не пропускайте mid: он может быть минимумом. Любой из этих шагов сохраняет обещание и сужает диапазон, а когда lo сравняется с hi, единственное оставшееся значение будет минимумом.

Проследим первый пример: [11, 13, 15, 17, 2, 5, 9]. В диапазоне от 0 до 6 середина — 3, значение 17, оно больше nums[6] = 9, поэтому lo становится равным 4. В диапазоне от 4 до 6 середина — 5, значение 5, оно не больше 9, поэтому hi становится равным 5. В диапазоне от 4 до 5 середина — 4, значение 2, оно не больше 5, поэтому hi становится равным 4. Верните nums[4] = 2.

На каждом шаге диапазон делится пополам, поэтому цикл выполняется не более примерно log2(n) раз: 13 шагов для 5000 элементов, при этом используются два индекса дополнительной памяти.

Алгоритм

Установите lo = 0 и hi = n-1.
Пока lo < hi, вычисляйте mid = lo + (hi - lo) / 2.
Если nums[mid] > nums[hi], установите lo = mid + 1.
Иначе установите hi = mid.
Когда цикл завершится, верните nums[lo].

def findMin(nums):
    lo, hi = 0, len(nums) - 1  # the minimum sits in nums[lo..hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the values drop after mid, so the minimum is right of it
        else:
            hi = mid      # nums[mid..hi] climbs: the minimum is at mid or left of it
    return nums[lo]

Ловушки и крайние случаи

Цикл состоит из четырёх строк, и в каждой есть соблазнительный неправильный вариант.

Запись hi = mid - 1 во второй ветви. Эта ветвь выполняется, когда mid может указывать на сам минимум. В [3, 1, 2] среднее значение 1 не больше 2, поэтому hi становится равным 0, и функция возвращает 3.
Цикл с условием lo ≤ hi. Когда lo становится равным hi, mid равен им обоим, nums[mid] > nums[hi] ложно, а присваивание hi = mid ничего не меняет: цикл никогда не заканчивается. Остановитесь, когда в диапазоне останется один элемент, используя условие lo < hi.
Сравнение с nums[lo] вместо nums[hi]. В невращённом списке [1, 2, 3, 4, 5] среднее значение 3 больше nums[0] = 1, и кажется, что место разрыва находится справа, поэтому поиск уходит от настоящего минимума с индексом 0 и возвращает 4.
Возврат lo вместо nums[lo]. В задаче требуется значение; индекс отвечает на другой вопрос (см. FAQ о количестве поворотов).
Предположение, что список был повёрнут. Поворот на 0 разрешён, и код, который ищет место разрыва, не предусматривая запасной вариант, выходит за пределы списка или ничего не возвращает. Если разрыва нет, верните nums[0].

Частые вопросы4

Какова временная сложность поиска минимального элемента в повернутом отсортированном массиве?

Время O(log n) и дополнительная память O(1) при бинарном поиске. На каждом шаге остаётся половина диапазона, поэтому для списка из 5000 элементов требуется не более 13 сравнений. Поиск точки разрыва выполняется за O(n): он считывает каждый элемент, если минимум находится в конце.

Почему сравнивать nums[mid] с nums[hi], а не с nums[lo]?

Потому что nums[hi] всегда позволяет определить, с какой стороны находится минимум, а nums[lo] — нет. Если nums[mid] > nums[hi], значения должны находиться между mid и hi; в противном случае nums[mid..hi] возрастает, и минимум находится в mid или до него. В случае с nums[lo] результат nums[mid] > nums[lo] подходит и для невращённого списка, где минимум — это nums[lo], и для вращённого, где он находится правее mid.

Как определить, сколько раз был повернут отсортированный массив?

Выполни тот же двоичный поиск и верни lo — индекс минимального элемента, а не nums[lo]. Если считать поворот перемещением последнего элемента в начало, этот индекс и будет количеством поворотов. Если считать его перемещением первого элемента в конец, как в этой задаче, количество равно (n - lo) mod n: в [11, 13, 15, 17, 2, 5, 9] минимальный элемент находится по индексу 4, а 7 минус 4 даёт 3 перемещённых значения.

Работает ли бинарный поиск, если в массиве есть дубликаты?

Не остаётся неизменным. В [2, 2, 2, 0, 2] nums[mid] может быть равно nums[hi], и тогда нельзя исключить ни одну из сторон. В этом случае безопасно сужать диапазон с помощью hi = hi - 1, поскольку копия nums[hi] остаётся в диапазоне на позиции mid, но поиск в списке из одинаковых значений, среди которых скрыто одно меньшее значение, тогда занимает O(n).

Python

def findMin(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [11, 13, 15, 17, 2, 5, 9]

Ожидается