假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如,數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。
請找出其中最小的元素。
你可以假設數組中不存在重復元素。
示例 1:
輸入: [3,4,5,1,2]
輸出: 1
示例 2:
輸入: [4,5,6,7,0,1,2]
輸出: 0
這道尋找最小值的題目可以用二分查找法來解決,時間復雜度為O(logN),空間復雜度為O(1)。
看一下代碼:
首先說一下主要思路:
單調遞增的序列:
*
*
*
*
*
做了旋轉:
*
*
*
*
*
用二分法查找,需要始終將目標值(這里是最小值)套住,并不斷收縮左邊界或右邊界。
左、中、右三個位置的值相比較,有以下幾種情況:
左值 《 中值, 中值 《 右值 :沒有旋轉,最小值在最左邊,可以收縮右邊界
右
中
左
左值 》 中值, 中值 《 右值 :有旋轉,最小值在左半邊,可以收縮右邊界
左
右
中
左值 《 中值, 中值 》 右值 :有旋轉,最小值在右半邊,可以收縮左邊界
中
左
右
左值 》 中值, 中值 》 右值 :單調遞減,不可能出現
左
中
右
分析前面三種可能的情況,會發現情況1、2是一類,情況3是另一類。
如果中值 《 右值,則最小值在左半邊,可以收縮右邊界。
如果中值 》 右值,則最小值在右半邊,可以收縮左邊界。
通過比較中值與右值,可以確定最小值的位置范圍,從而決定邊界收縮的方向。
而情況1與情況3都是左值 《 中值,但是最小值位置范圍卻不同,這說明,如果只比較左值與中值,不能確定最小值的位置范圍。
所以我們需要通過比較中值與右值來確定最小值的位置范圍,進而確定邊界收縮的方向。
接著分析解法里的一些問題:
首先是while循環里的細節問題。
這里的循環不變式是left 《 right, 并且要保證左閉右開區間里面始終套住最小值。
中間位置的計算:mid = left + (right - left) / 2
這里整數除法是向下取整的地板除,mid更靠近left,
再結合while循環的條件left 《 right,
可以知道left 《= mid,mid 《 right,
即在while循環內,mid始終小于right。
因此在while循環內,nums[mid]要么大于要么小于nums[right],不會等于。
這樣else {right = mid;}這句判斷可以改為更精確的
else if (nums[mid] 《 nums[right]) {right = mid;}。
再分析一下while循環退出的條件。
如果輸入數組只有一個數,左右邊界位置重合,left == right,不會進入while循環,直接輸出。
如果輸入數組多于一個數,循環到最后,會只剩兩個數,nums[left] == nums[mid],以及nums[right],這里的位置left == mid == right - 1。
如果nums[left] == nums[mid] 》 nums[right],則左邊大、右邊小,
需要執行left = mid + 1,使得left == right,左右邊界位置重合,循環結束,nums[left]與nums[right]都保存了最小值。
如果nums[left] == nums[mid] 《 nums[right],則左邊小、右邊大,
會執行right = mid,使得left == right,左右邊界位置重合,循環結束,nums[left]、nums[mid]、nums[right]都保存了最小值。
細化了的代碼:
再討論一個問題:
為什么左右不對稱?為什么比較mid與right而不比較mid與left?能不能通過比較mid與left來解決問題?
左右不對稱的原因是:
這是循環前升序排列的數,左邊的數小,右邊的數大,而且我們要找的是最小值,肯定是偏向左找,所以左右不對稱了。
為什么比較mid與right而不比較mid與left?
具體原因前面已經分析過了,簡單講就是因為我們找最小值,要偏向左找,目標值右邊的情況會比較簡單,容易區分,所以比較mid與right而不比較mid與left。
那么能不能通過比較mid與left來解決問題?
能,轉換思路,不直接找最小值,而是先找最大值,最大值偏右,可以通過比較mid與left來找到最大值,最大值向右移動一位就是最小值了(需要考慮最大值在最右邊的情況,右移一位后對數組長度取余)。
以下是先找最大值的代碼,可以與前面找最小值的比較:
使用left 《 right作while循環條件可以很方便推廣到數組中有重復元素的情況,即154題:
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
只需要在nums[mid] == nums[right]時挪動右邊界就行:
初始條件是左閉右閉區間,right = nums.size() - 1,
那么能否將while循環的條件也選為左閉右閉區間left 《= right?
可以的,代碼如下:
-
C語言
+關注
關注
180文章
7598瀏覽量
136188 -
leetcode
+關注
關注
0文章
20瀏覽量
2311
發布評論請先 登錄
相關推薦
評論