Эта статья является частью серии статей Натана Томаса, разработчика программного обеспечения полного стека, работающего в Сан-Франциско, Калифорния. Среди других его недавних статей — Создание собственного биткойн-узла и Подмассив максимального продукта.

Введение

Если вы ищете краткое руководство по оптимальному решению задачи LeetCode Найти минимум в массиве с вращающейся сортировкой, добро пожаловать. 🔥

Это вопрос из Списка вызовов кода для Blind 75 LeetCode, группы вопросов, составленной техническим руководителем Facebook, который рекламируется как действительно хороший способ подготовиться к собеседованию.

Не корите себя слишком сильно, если вы здесь, потому что вам пришлось нелегко. У всех иногда возникают трудности с кодированием.

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

Начальная настройка 👷🏻‍♂️

Первое, что мы всегда должны пытаться сделать, это понять все правила для нашей задачи, прежде чем писать хоть одну строчку кода (см. Техники решения проблем Поля):

  1. Нам будет предоставлен список nums
  2. Значения будут отсортированы
  3. Однако значения могут быть повернуты от конца к началу (например, [1, 2, 3, 4, 5] может быть повернуто как [3, 4, 5, 1, 2]) и переданы нам как значение nums
  4. Мы должны вернуть минимальное значение в списке
  5. Список nums длины будет 1 <= len(nums) <= 5000
  6. Все целые числа в качестве значений в nums будут уникальными.
  7. Мы должны сделать это в O(log n) раз

Фух. Это звучит немного сложно, особенно если вы раньше не сталкивались с подобной проблемой.

Это нормально. Вот почему ты здесь со мной. Разберемся вместе.

Я буду использовать Python для ответа на этот вопрос, поскольку он немного похож на универсальный язык — предпочитаете ли вы JavaScript, Java, Golang, C или что-то еще, каждый может «отчасти» читать Python.

Мы также сразу перейдем к «оптимальному» решению. Если вы чем-то похожи на меня, вы уже пытались решить эту проблему, прежде чем искать ответ. Я собираюсь убедиться, что вы получите хороший.

Давайте начнем.

Настройка переменных и логика ✅

То, что действительно превращает эту задачу из простого в средний уровень сложности, заключается в том, что мы должны сделать это за быстрее, чем O(n) (линейное) время, поскольку правила гласят, что мы должны найти числа через O(log n) раз. Это означает, что мы не можем просто просмотреть список nums и отследить наименьшее число, которое мы видели до сих пор.

К счастью, правило, дающее нам временную сложность попадания, также является огромной подсказкой!

Какой знаменитый алгоритм работает с временной сложностью O(log n)? Это верно! Бинарный поиск!

Сегодня мы напишем модифицированный бинарный поиск, чтобы просмотреть наш список nums и найти минимум.

Что нам нужно для бинарного поиска? Что ж, нам нужно несколько указателей с поворотом между ними каждый раз, чтобы угадывать среднюю точку, сравнивать и сбрасывать наши боковые указатели.

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

  1. Если значение среднего указателя (поворотного) отсортированного и повернутого списка меньше, чем значение левого указателя, наименьшее число находится либо в опорной точке, либо в левой части списка.
  2. Если средний (стержень) больше левого указателя, наименьшее число находится в правой части списка.
  3. Наименьшим числом всегда является число, значение которого index — 1 больше его (например, nums = [4, 5, 6, 1, 2, 3], где 1 — наименьшее)

Например, предположим, что у нас есть отсортированный и повернутый список, который выглядит так:

nums = [6, 7, 1, 2, 3, 4, 5]

Обратите внимание, что средняя точка, 2, меньше левого указателя, и как это указывает на то, что минимум (то есть 1) находится в левой части?

Теперь обратите внимание, что произойдет, если мы еще больше повернем этот же список:

nums = [4, 5, 6, 7, 1, 2, 3]

Со средней точкой 7 наше минимальное число теперь надежно находится в правой части списка. Вы можете попробовать поэкспериментировать с этим списком (или с другим списком), и результат всегда будет одним и тем же — средняя точка решает, нужно ли искать минимальное число слева или справа.

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

Ну вот. Я думаю, что у нас есть маршрут, чтобы двигаться вперед сейчас. Давайте продолжим и настроим наши исходные переменные:

Мы начнем наш указатель left с индекса 0, а указатель right с конечного индекса списка nums.

Обратите внимание, что здесь мы также добавили оператор if. Это потому, что наш список из nums имеет потенциальную минимальную длину 1. Если это так, все может стать немного грязным, верно?

Вместо этого мы просто отправим это значение обратно, так как это, очевидно, минимальное значение в списке длиной 1.

Отсюда мы можем приступить к построению нашего цикла for!

Создаем наш цикл 🔁

Мы будем использовать цикл while для этого процесса, так как мы хотели бы продолжать итерацию, пока наша переменная left меньше, чем наша right (точно так же, как при обычном бинарном поиске).

Кроме того, нам нужно (для каждой итерации нашего цикла) выбрать опорную точку в середине текущего списка, чтобы выполнить наше сравнение. Чтобы надежно выбрать это pivot для будущих итераций, когда наши указатели left и right будут обновлены, нам нужно вычесть значение left из right, выполнить деление по этажам на 2 (Python позволяет деление по этажам с помощью оператора //), а затем добавьте значение left обратно.

Вот как это выглядит:

Следующее, что нам нужно сделать, это создать несколько операторов if/else, которые проверяют, нашли ли мы здесь минимальное число (или же обновляют наши указатели).

Вот тут-то и вступает в действие логика, о которой мы говорили ранее в этой статье. Оказывается, минимальное число всегда будет, когда позиция i меньше i — 1. Это имеет смысл, верно? Если у нас есть такой список:

nums = [4, 5, 6, 7, 1, 2, 3]

Минимальное число, 1, — это единственное число, в котором оно меньше числа, непосредственно предшествующего ему.

Мы можем воспользоваться этим, чтобы написать наши проверки следующим образом:

Берем пивот и проверяем:

  1. Если число после pivot меньше pivot (это означает, что число после pivot является минимальным)
  2. Если число перед pivot больше, чем pivot (что означает, что точка поворота является минимальной)

Если любой из них равен True, мы возвращаем правильное минимальное число.

Если ни один из них не равен True, мы обновляем указатель right на pivot, если значение индекса pivot меньше указателя right. Помните наше предыдущее обсуждение поиска минимума при ротации отсортированного списка?

Если это не так, мы вернемся к обновлению нашего указателя left, чтобы он стал pivot.

Ну вот. Это дает нам окончательный алгоритм. Есть много мелочей, которые вы можете сделать, чтобы упростить синтаксис для этого, но я сделал все возможное, чтобы было предельно ясно, что происходит, когда я писал это здесь.

Это решение будет работать с временной сложностью O(log n) и пространственной сложностью O(1), поскольку мы всегда используем одинаковое количество переменных-указателей.

Заключение

Поздравляю 🎉

Я знаю, что это было немного длинно, но, надеюсь, теперь вы чувствуете себя намного увереннее, приступая к проблемам такого рода!

Следите за остальными статьями Слепые 75 проблем с программированием от меня. Я собираюсь решать их и публиковать по ходу дела.

Кроме того, не стесняйтесь обращаться ко мне по любой из приведенных ниже ссылок, если вы хотите поговорить о кодировании, крутых технологиях или о чем-то еще (мне очень, очень нравятся рекомендации книг).

Спасибо за прочтение!

Натан

(GitHub, LinkedIn, Twitter и Персональный сайт)