154. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 II
題目
已知一個長度為 n 的數(shù)組悯搔，預(yù)先按照升序排列照弥，經(jīng)由 1 到 n 次 旋轉(zhuǎn) 后杉编，得到輸入數(shù)組。例如养叛，原數(shù)組 nums = [0,1,4,4,5,6,7] 在變化后可能得到：
若旋轉(zhuǎn) 4 次，則可以得到 [4,5,6,7,0,1,4]
若旋轉(zhuǎn) 7 次凑兰，則可以得到 [0,1,4,4,5,6,7]
注意闹啦，數(shù)組 [a[0], a[1], a[2], ..., a[n-1]] 旋轉(zhuǎn)一次 的結(jié)果為數(shù)組 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
給你一個可能存在 重復(fù) 元素值的數(shù)組 nums 色乾，它原來是一個升序排列的數(shù)組誊册，并按上述情形進(jìn)行了多次旋轉(zhuǎn)。請你找出并返回數(shù)組中的 最小元素 暖璧。
解題思路
這道題和昨天的比較像案怯，但是多了重復(fù)元素。
昨天的思路我們是我們通過比較num[mid]和num[right]的大小澎办，確認(rèn)最小元素的區(qū)間嘲碱。但是如果有了重復(fù)元素，則他們可能相等局蚀，這個時候麦锯，我們是不知道最小元素的區(qū)間的。但是我們可以確認(rèn)最小元素一定不是 num[right] ,所以可以把區(qū)間減小1
代碼實現(xiàn)
func findMin(nums []int) int {
i,j := 0,len(nums)-1
for i<j{
mid := (i+j)/2
if nums[mid]>nums[j]{
i = mid+1
} else if nums[mid]<nums[j]{
j = mid
}else{
j--
}
}
return nums[i]
}
func min(a,b int)int{
if a<b{
return a
}
return b
}
