1.題目
假設按照升序排序的陣列在預先未知的某個點上進行了旋轉，例如，陣列 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] ，
請找出其中最小的元素，
示例 1：
輸入：nums = [3,4,5,1,2]
輸出：1
示例 2：
輸入：nums = [4,5,6,7,0,1,2]
輸出：0
示例 3：
輸入：nums = [1]
輸出：1
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
2.時間復雜度O(n)的解法
2.1 思路
本思路是概括了題目和修改后的題目，暴力破解都是這個方法，
原陣列是非遞減的，旋轉后，有兩種情況，陣列仍是非遞減的，例如將全部元素放到陣列的末尾，它相當于還是原陣列，或者有重復項，例如 {2，2，2，2}，旋轉后仍是非遞減的，那么我們回傳第一個元素即可，另一種情況就會出現前一個元素大于后一個元素，那么后一個元素一定是最小的，也就是我們要的解，
2.2 代碼
int findMin(vector<int>& nums) {
if(!nums.size()) return -1;
for(int i = 0; i < nums.size() - 1; i++) {
if(nums[i] > nums[i + 1])
return nums[i + 1];
}
return nums[0];
}
3.時間復雜度O(logn)的解法
3.1 思路
此思路是假設沒有重復的數，
我們知道，當陣列是已經排序好的，我們可以用二分法來查找，其實本題也可以利用二分法來做，
我們找一個中間值，如果這個中間值小于此時的left，那么就意味著我們要找的數就在left 到 mid 中間，如果中間值大于left，那么我們要找的值就在mid到right中間,直到縮減到兩個數的時候，此時左指標指向的數一定大于右指標指向的數，mid此時就會在左指標的位置上，我們回傳右指標即可
3.2 代碼
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
int mid = (left + right) / 2;
if (nums[left] < nums[right])
{
return nums[left];
}
while (left != mid)
{
if (nums[mid] > nums[left])
{
left = mid;
}
else if (nums[mid] < nums[right])
{
right = mid;
}
mid = (left + right) / 2;
}
return nums[right];
}
};
4.修改后的題(允許元素重復)
4.1題目
把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉，
輸入一個升序的陣列的一個旋轉，輸出旋轉陣列的最小元素，
例如陣列{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該陣列的最小值為1，
陣列可能包含重復項，
注意：陣列內所含元素非負，若陣列大小為0，請回傳-1，
樣例
輸入：nums=[2,2,2,0,1]
輸出：0
題目地址
4.2解法
題目中允許出現重復的數字，這就意味著在原來的理解上我們要多一層可能，那就是中間的值等于左側值或者右側的值，舉一個例子[2,2,2,1,1,2]，此時mid指向第三個2,最小值在mid的右側；[2,2,2,1,1,2,2,2,2,2,2],此時最小值在mid左側，這樣我們就需要來判斷此時我們是要在左側尋找還是在右側尋找了，但不管怎么樣，如果相同，我們可以省略掉相同的數的那個指標，
所以分三種情況，當中間的比最右端的小，此時我們讓右指標移動過來，當中間的比右邊打，我們讓左指標移到中間指標的后方，如果相等，就讓右指標移動，
4.3代碼
class Solution {
public:
int findMin(vector<int>& nums) {
int low = 0;
int high = nums.size() - 1;
while (low < high) {
int pivot = low + (high - low) / 2;
if (nums[pivot] < nums[high]) {
high = pivot;
}
else if (nums[pivot] > nums[high]) {
low = pivot + 1;
}
else {
high -= 1;
}
}
return nums[low];
}
};
詳細內容可以看這里，講的真的很好，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260497.html
標籤：其他
上一篇：重塑矩陣
下一篇：docker03-常用命令