Найдите наименьшее число в отсортированном вращающемся массиве
Я столкнулся с этим вопросом в одном интервью. Пожалуйста, помогите мне найти решение.
Вопрос:
Вы отсортировали вращающийся массив, т.е. е.массив содержит элементы, которые отсортированы, и его можно вращать по кругу, например, если элементы в массиве равны [5,6,10,19,20,29], тогда первый поворот массива становится [29,5,6,10,19 , 20] и во второй раз становится [20,29,5,6,10,19] и так далее.
Итак, вам нужно найти наименьший элемент в массиве в любой точке. Вам не будет предоставлено количество поворотов массива. Просто задайте повернутые элементы массива и найдите среди них самый маленький. В этом случае на выходе должно быть 5.
1 ответ
Это - мое pythonic решение с помощью рекурсии:
Временная сложность является O (журнал (n)) & сложность Пространства: O (1)
class Solution(object):
def findMin(self, nums):
left = 0
right = len(nums) -1
mid = len(nums) // 2
if len(nums) == 0:
return -1
if len(nums) == 1:
return nums[left]
if len(nums) == 2:
return min(nums[left], nums[right])
if nums[left] < nums[right]:
return nums[left]
elif nums[mid] > nums[left]:
return self.findMin(nums[mid + 1: ])
elif nums[mid] < nums[left]:
return self.findMin(nums[: mid + 1])