Сложность: Hard
Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,4,4,5,6,7] может стать: [4,5,6,7,0,1,4], если он был повернут 4 раза. [0,1,4,4,5,6,7], если он был повернут 7 раз. Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Для данного отсортированного и повернутого массива nums, который может содержать дубликаты, верните минимальный элемент этого массива. Необходимо максимально уменьшить количество операций.
Пример:
Input: nums = [1,3,5]
Output: 1
👨💻 Алгоритм:
1️⃣Сравнение с правой границей: В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]).
2️⃣Обновление указателей: Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid. Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid. Если nums[mid] == nums[high], мы не можем быть уверены, в какой половине находится минимальный элемент из-за наличия дубликатов. В этом случае безопасно сдвинуть правый указатель на один шаг влево (high = high - 1), чтобы сузить область поиска без пропуска возможного минимального элемента.
3️⃣Итерация до сужения диапазона поиска: Продолжаем процесс, пока левый указатель не встретится с правым. В конечном итоге правый указатель укажет на минимальный элемент массива после всех поворотов.
😎 Решение:
class Solution:
def findMin(self, nums: List[int]) -> int:
low = 0
high = len(nums) - 1
while high > low:
pivot = low + (high - low) // 2
if nums[pivot] < nums[high]:
high = pivot
elif nums[pivot] > nums[high]:
low = pivot + 1
else:
high -= 1
return nums[low]
Ставь 👍 и забирай 📚 Базу знаний