题目:
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 注意数组中可能存在重复的元素。
思路:
仍然使用二分法,考虑到会存在重复元素的情况,因此当判断到有重复数字时(nums[middle] == nums[tail])时,使用tail--。
程序:
class Solution:
def findMin(self, nums: List[int]) -> int:
length = len(nums)
if length <= 0:
return 0
if length == 1:
return nums[0]
head = 0
tail = length - 1
while head < tail:
middle = (head + tail) // 2
if nums[middle] > nums[tail]:
head = middle + 1
elif nums[middle] < nums[tail]:
tail = middle
else:
tail -= 1
output = head
return nums[head]
Leetcode练习(Python):数组类:第154题:假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 注意数组中可能存在重复的元素。
原文:https://www.cnblogs.com/zhuozige/p/12774054.html