題目鏈接

?

/**

? ? ? ? 數組在某處進行旋轉,分割為兩個獨立的遞增區間,找出數組的最小值;特殊情況:若旋轉次數是數組長度的倍數,則數組不變

? ? ? ? 特點:

? ? ? ? ? ? 常規情況:

? ? ? ? ? ? ? ? 數組被分割為兩個獨立的子區間,左半區的最小值大于右半區的最大值

? ? ? ? ? ? ? ? 依據數組長度,mid可能落在左半區也有可能落在右半區,最小值在右半區

? ? ? ? ? ? 特殊情況:

? ? ? ? ? ? ? ? 旋轉次數是數組長度的倍數,則數組不變

? ? ? ? ? ? ? ? 此時數組是一個完整的遞增區間,取第一個元素即可

? ? ? ? 二分策略:

? ? ? ? ? ? 若left與right已經在一個遞增區間中,則直接返回nums[left]即可;本身就是一個遞增區間,或經過收縮left來到了右半區。

? ? ? ? ? ? 若不在一個區間中,則判斷mid所在半區;在左半區則淘汰[left,mid],在右半區則淘汰[mid,right]

? ? ? ? ? ? 經過收縮后再重新判斷left,right是否在同一區間,在則直接返回結果,不在則重復上述流程再次收縮

? ? ? ? 判斷條件:

? ? ? ? ? ? nums[left] <= nums[mid] && nums[mid] <= nums[right] ---> [left,right]已經在同一區間,直接返回結果即可

? ? ? ? ? ? 僅滿足:nums[left] <= nums[mid] ---> [left,right]不單調,且mid在左半區; 淘汰[left,mid]

? ? ? ? ? ? 均不滿足,[left,right]不單調,且mid在右半區; 淘汰[mid,right)

*/

class Solution {/**數組在某處進行旋轉,分割為兩個獨立的遞增區間,找出數組的最小值;特殊情況:若旋轉次數是數組長度的倍數,則數組不變特點:常規情況:數組被分割為兩個獨立的子區間,左半區的最小值大于右半區的最大值依據數組長度,mid可能落在左半區也有可能落在右半區,最小值在右半區特殊情況:旋轉次數是數組長度的倍數,則數組不變此時數組是一個完整的遞增區間,取第一個元素即可二分策略:若left與right已經在一個遞增區間中,則直接返回nums[left]即可;本身就是一個遞增區間,或經過收縮left來到了右半區。若不在一個區間中,則判斷mid所在半區;在左半區則淘汰[left,mid],在右半區則淘汰[mid,right]經過收縮后再重新判斷left,right是否在同一區間,在則直接返回結果,不在則重復上述流程再次收縮判斷條件:nums[left] <= nums[mid] && nums[mid] <= nums[right] ---> [left,right]已經在同一區間,直接返回結果即可僅滿足:nums[left] <= nums[mid] ---> [left,right]不單調,且mid在左半區; 淘汰[left,mid]均不滿足,[left,right]不單調,且mid在右半區; 淘汰[mid,right)*/public int findMin(int[] nums) {//雙指針置于有效部分兩端int left = 0, right = nums.length - 1;while(left <= right) {int mid = (left + right) >>> 1;//[left,right]已收縮至右半區直接返回結果即可if(nums[left] <= nums[mid] && nums[mid] <= nums[right]) {return nums[left];}//[left,right]不單調,且mid在左半區else if(nums[left] <= nums[mid]) { left = mid + 1; //淘汰[left,mid]}//[left,right]不單調,且mid在右半區else {right = mid; //淘汰[mid,right) ---> mid恰好為右半區第一個元素,避免錯失最小值}}return -1;}
}