主題
題目連結(jié)：
題目意譯：
假設(shè)現(xiàn)有一個(gè)長(zhǎng)度為 n 且按升序排序之陣列被旋轉(zhuǎn)了 1 到 n 次。例如陣列 nums = [0,1,4,4,5,6,7] 可能變?yōu)椋?/div>
[4,5,6,7,0,1,4] 如果它被旋轉(zhuǎn)了 4 次。
[0,1,4,4,5,6,7] 如果它被旋轉(zhuǎn)了 7 次。
注意旋轉(zhuǎn)一個(gè)陣列 [a[0], a[1], a[2], ……, a[n-1]] 一次將得到陣列 [a[n-1], a[0], a[1], a[2], ……, a[n-2]]。
給定已排序的、旋轉(zhuǎn)後的、可能包含重複元素的陣列 nums，回傳該陣列中最小的元素。
你必須盡可能地減少總體所需操作步驟數(shù)。
限制：
n == nums.length
1 ≦ n ≦ 5000
-5000 ≦ nums[i] ≦ 5000
nums 已排序且旋轉(zhuǎn)了 1 到 n 次。
進(jìn)階：本題類(lèi)似於 Find Minimum in Rotated Sorted Array，但是 nums 可能包含重複的數(shù)字。試問(wèn)這是否會(huì)影響時(shí)閒複雜度？如何影響且為何？
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = [1,3,5]
輸出： 1
範(fàn)例 2：
輸入： nums = [2,2,2,0,1]
輸出： 0
解題思維：
當(dāng) nums 中的數(shù)字大部分相異時(shí)，這題的二分搜尋法（Binary Search）已經(jīng)是個(gè)相當(dāng)好的選擇了。當(dāng)然，因?yàn)楸绢}包含重複的元素，所以需要修改一下。原先只有把情況分成，nums[M] > nums[R] 以及 nums[M] ≦ nums[R] 兩種。而現(xiàn)在我們需要把所有可能拆開(kāi)：
當(dāng) nums[M] > nums[R] 時(shí)跟原先一致，代表著 nums[L] ～ nums[M] 都會(huì)大於 nums[R]，因此最小的元素應(yīng)位於 [M + 1, R] 這個(gè)範(fàn)圍。所以我們將 L 之值更新為 M + 1；
當(dāng) nums[M] < nums[R] 時(shí)則與上面相對(duì)，代表著 nums[L] ～ nums[M] 都會(huì)小於 nums[R]，因此最小的元素應(yīng)位於 [L, M] 這個(gè)範(fàn)圍。所以我們將 R 之值更新為 M；
以及本次的重點(diǎn)——當(dāng) nums[M] = nums[R] 時(shí)，我們只能確定 nums[R] 與 nums[M] 一樣大以外，其他資訊一論無(wú)法推得。因此我們能做的只有將 R 之值更新為 R - 1。
而這便可以解答進(jìn)階的部分之問(wèn)題：最糟的情況發(fā)生於 nums 中所有元素相同，此時(shí)上述的二分搜尋法將派不上用場(chǎng)。因此時(shí)間複雜度會(huì)降為 O(n)。但是大部分情況數(shù)字的差異足夠地多，使得平均時(shí)間複雜度依舊落於 O(log n)。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
