Постановка задачи :
Вам дан отсортированный массив, который теперь был повернут «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 - это минимальный элемент.
Подход :
Оптимизированный подход
Как указано в самой подсказке, мы хотим уменьшить пространство поиска, чтобы оптимизировать наше решение. Следовательно, мы хотим применить для этого технику «разделяй и властвуй». Для этого используйте алгоритм двоичного поиска.
- Начнем с создания двух переменных с именами low и high, где low = 0, а high = n-1. Теперь мы запускаем цикл, который будет работать до low ‹= high. Мы также делаем еще одну переменную mid, которая равна (low + high) / 2.
- Теперь делаем 4 случая и соответственно решаем нашу задачу.
- Случай 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 для ежедневного обучения.