Алгоритмы и структуры данных

Найти минимум в повернутом отсортированном массиве

Проблема: Дан массив длины n, который изначально был отсортирован по возрастанию. Далее его поворачивали от 1 до n раз. Например, массив nums = [1,2,3,4,5,6] может выглядеть следующим образом:
[3,4,5,6,1,2], если его повернули 4 раза.
[1,2,3,4,5,6], если он был повернут 6 раз.

Обратим внимание, что поворот массива 4 раза перемещает последние четыре элемента массива в начало. Вращение массива 6 раз дает исходный массив.

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

Пример 1: Input: nums = [3,4,5,6,1,2]
Output: 1

Пример 2: Input: nums = [4,5,0,1,2,3]
Output: 0

www.tgoop.com/the_algorithms/4888

4.3K viewsNov 27, 2024 at 12:30

Найти минимум в повернутом отсортированном массиве

Проблема: Дан массив длины n, который изначально был отсортирован по возрастанию. Далее его поворачивали от 1 до n раз. Например, массив nums = [1,2,3,4,5,6] может выглядеть следующим образом:
[3,4,5,6,1,2], если его повернули 4 раза.
[1,2,3,4,5,6], если он был повернут 6 раз.

Обратим внимание, что поворот массива 4 раза перемещает последние четыре элемента массива в начало. Вращение массива 6 раз дает исходный массив.

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

Пример 1: Input: nums = [3,4,5,6,1,2]
Output: 1

Пример 2: Input: nums = [4,5,0,1,2,3]
Output: 0

BY Алгоритмы и структуры данных