154. 尋找旋轉排序陣列中的最小值 II
已知一個長度為 n 的陣列，預先按照升序排列，經由 1 到 n 次 旋轉 后，得到輸入陣列，例如，原陣列 nums = [0,1,4,4,5,6,7] 在變化后可能得到：
若旋轉 4 次，則可以得到 [4,5,6,7,0,1,4]
若旋轉 7 次，則可以得到 [0,1,4,4,5,6,7]
注意，陣列 [a[0], a[1], a[2], …, a[n-1]] 旋轉一次 的結果為陣列 [a[n-1], a[0], a[1], a[2], …, a[n-2]] ，
給你一個可能存在 重復 元素值的陣列 nums ，它原來是一個升序排列的陣列，并按上述情形進行了多次旋轉，請你找出并回傳陣列中的 最小元素 ，
示例 1：
輸入：nums = [1,3,5]
輸出：1
示例 2：
輸入：nums = [2,2,2,0,1]
輸出：0
思路：
這題最簡單的解法就是遍歷一次陣列，記錄最小值，但是沒有利用到陣列是有序的條件，O(N)的空間復雜度是無法通過這題的，
我們可以利用二分法來解決這道題，
假定給出排序后陣列arr，
通過觀察可以發現，旋轉后的陣列中有兩個有序的子陣列，而且左右的元素都比左邊大，
當 arr[mid] 大于 arr[left] ，那么mid一定在左邊這個子陣列里，
當 arr[mid] 小于 arr[right] ，說明mid在右邊這個子陣列里，
所以，當 arr[mid] 大于 arr[left] 的時候（就如圖示），那么最小的數一定不在左子陣列，此時讓left移動到mid處，
當 arr[mid] 小于 arr[right] 說明最小值就在右邊這個子陣列里，讓right移動到mid處，
讓更新后的 left 和 right 繼續下一次查找，
查找程序
left 永遠都在左子陣列，right都在右子陣列，經過一輪輪的查找，它們會逐漸靠近，最終它們會處于相鄰位置，這就是查找結束條件 ，此時 arr[right] 就是最小值，
特殊情況：
要注意，當三個下標指向的值相同時，此時無法判斷，只能遍歷查找，
代碼示例：
int findMin(int* nums, int numsSize){
int left = 0;
int right = numsSize - 1;
//當陣列有序或者陣列只有一個元素 直接回傳第一個元素，
if (nums[left] < nums[right] || left == right)
{
return nums[left];
}
//當left和right相鄰就停止
while(left + 1 != right)
{
int mid = (left + right)/2;
if(nums[mid] < nums[right])
{
right = mid;
}
else if(nums[mid] > nums[left])
{
left = mid;
}
else
{ //left right mid 下標指向的數相同只能遍歷，
return getMin(nums,left,right);
}
}
return nums[right];
}
int getMin(int* nums,int left,int right)
{
int min = nums[left];
int i;
for(i=left+1;i<=right;i++)
{
if(nums[i]<min)
min = nums[i];
}
return min;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/277072.html
標籤：其他
上一篇：如何吃透一個java專案