做網(wǎng)站baidunongmin南寧seo優(yōu)化公司
?劍指 Offer 11. 旋轉(zhuǎn)數(shù)組的最小數(shù)字
難度:簡單
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾,我們稱之為數(shù)組的旋轉(zhuǎn)。
給你一個可能存在 重復 元素值的數(shù)組 numbers
,它原來是一個升序排列的數(shù)組,并按上述情形進行了一次旋轉(zhuǎn)。請返回旋轉(zhuǎn)數(shù)組的最小元素。例如,數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一次旋轉(zhuǎn),該數(shù)組的最小值為 1。
注意,數(shù)組 [a[0], a[1], a[2], ..., a[n-1]]
旋轉(zhuǎn)一次 的結果為數(shù)組 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。
示例 1:
輸入:numbers = [3,4,5,1,2]
輸出:1
示例 2:
輸入:numbers = [2,2,2,0,1]
輸出:0
提示:
n == numbers.length
1 <= n <= 5000
-5000 <= numbers[i] <= 5000
numbers
原來是一個升序排序的數(shù)組,并進行了1
至n
次旋轉(zhuǎn)
注意:本題與 154. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 II 相同。
💡思路:二分查找
將旋轉(zhuǎn)數(shù)組對半分可以得到一個包含最小元素的新旋轉(zhuǎn)數(shù)組,以及一個非遞減排序的數(shù)組。新的旋轉(zhuǎn)數(shù)組的長度是原數(shù)組的一半,從而將問題規(guī)模減少了一半,這種折半性質(zhì)的算法的時間復雜度為 O ( l o g 2 N ) O(log2N) O(log2N)。
此時問題的關鍵在于確定對半分得到的兩個數(shù)組哪一個是旋轉(zhuǎn)數(shù)組,哪一個是非遞減數(shù)組。我們很容易知道非遞減數(shù)組的第一個元素一定小于等于最后一個元素。
通過修改二分查找算法進行求解(left
、mid
、right
分別代表包含最小元素的新旋轉(zhuǎn)數(shù)組 左
、中
、右
):
- 當
numbers[mid] > numbers[right]
時,[left,mid]
區(qū)間內(nèi)的數(shù)組是非遞減數(shù)組,[mid + 1, right]
區(qū)間內(nèi)的數(shù)組為新的旋轉(zhuǎn)數(shù)組,此時,left = mid + 1
; - 當
numbers[mid] < numbers[right]
時,[mid,right]
區(qū)間內(nèi)的數(shù)組是非遞減數(shù)組,[left, mid]
區(qū)間內(nèi)的數(shù)組為新的旋轉(zhuǎn)數(shù)組,此時,right = mid
; - 當
numbers[mid] = numbers[right]
時, 無法判斷哪一個是旋轉(zhuǎn)數(shù)組,哪一個是非遞減數(shù)組,此時right- -
,直到能判斷。
🍁代碼:(C++、Java)
C++
class Solution {
public:int minArray(vector<int>& numbers) {int left = 0;int right = numbers.size() - 1;if(right == 0) return numbers[0];while(left < right){int mid = left + (right - left) / 2;if(numbers[mid] > numbers[right]){left = mid + 1;}else if(numbers[mid] < numbers[right]){right = mid;}else{right--;}}return numbers[left];}
};
Java
class Solution {public int minArray(int[] numbers) {int left = 0;int right = numbers.length - 1;if(right == 0) return numbers[0];while(left < right){int mid = left + (right - left) / 2;if(numbers[mid] > numbers[right]){left = mid + 1;}else if(numbers[mid] < numbers[right]){right = mid;}else{right--;}}return numbers[left];}
}
🚀 運行結果:
🕔 復雜度分析:
- 時間復雜度: O ( l o g n ) O(logn) O(logn),平均時間復雜度為 O ( l o g ? n ) O(log?n) O(log?n),其中
n
是數(shù)組numbers
的長度。如果數(shù)組是隨機生成的,那么數(shù)組中包含相同元素的概率很低,在二分查找的過程中,大部分情況都會忽略一半的區(qū)間。而在最壞情況下,如果數(shù)組中的元素完全相同,那么while
循環(huán)就需要執(zhí)行n
次,每次忽略區(qū)間的右端點,時間復雜度為O(n)
。 - 空間復雜度: O ( 1 ) O(1) O(1)。
題目來源:力扣。
放棄一件事很容易,每天能堅持一件事一定很酷,一起每日一題吧!
關注我LeetCode主頁 / CSDN—力扣專欄,每日更新!