Постановка задачи :

Вам дан отсортированный массив, который теперь был повернут «K» раз, что вам неизвестно. Вращение здесь означает, что каждый элемент сдвигается из своей позиции вправо при каждом повороте, а последний элемент просто перемещается в первую позицию. Например: 1 2 3 4, после одного поворота получается 4 1 2 3. Ваша задача найти минимальное число в этом массиве.

Пример ввода:

N = 4
Arr = {3 4 1 2}

Вывод:

1

Объяснение данных тестовых случаев:

Как ясно видно, наш исходный отсортированный массив был 1 2 3 4, и после одного поворота он стал 4 1 2 3, а после второго поворота он стал 3 4 1 2, который указан во входных данных, и здесь 1 - это минимальный элемент.

Подход :

Оптимизированный подход

Как указано в самой подсказке, мы хотим уменьшить пространство поиска, чтобы оптимизировать наше решение. Следовательно, мы хотим применить для этого технику «разделяй и властвуй». Для этого используйте алгоритм двоичного поиска.

  1. Начнем с создания двух переменных с именами low и high, где low = 0, а high = n-1. Теперь мы запускаем цикл, который будет работать до low ‹= high. Мы также делаем еще одну переменную mid, которая равна (low + high) / 2.
  2. Теперь делаем 4 случая и соответственно решаем нашу задачу.
  3. Случай 1: arr [low] ‹= arr [high]
  • Мы возвращаем arr [low], поскольку массив отсортирован, arr [low] будет минимальным элементом.

4. Теперь мы создаем переменную с именем next, которая будет равна (mid + 1)% n, и previous, которая будет равна (mid + n-1)% n.

5. Случай 2: (arr [mid] ‹= arr [next]) и (arr [mid]‹ = arr [previous])

  • Возвращаем arr [mid]. Мы делаем это, потому что при наблюдении мы видим, что только минимальный элемент будет иметь это особое свойство, если он меньше, чем оба его соседа. Пример 4 1 2 3, здесь вы можете видеть, что только 1, который является минимальным элементом, в данном случае является элементом, который меньше, чем оба его соседа 4 и 2.

6. Случай 3: arr [mid] ‹= arr [high]

  • Здесь мы видим, что если текущий средний элемент меньше текущего высокого элемента, это означает, что минимальный элемент не будет присутствовать в правой половине массива (относительно середины). Следовательно, мы отбрасываем это пространство поиска и делаем high = mid-1.

7. Случай 4: arr [mid] ›= arr [low]

  • Этот случай аналогичен случаю 3, с той лишь разницей, что здесь мы можем наблюдать, что если наш текущий средний элемент больше текущего нижнего элемента, минимальный элемент не будет присутствовать в левой половине массива (со ссылкой на середина). Следовательно, мы отбрасываем это пространство поиска и делаем low = mid + 1.

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

Код:

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

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

Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.