旋轉數組的最小數字

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]

來源：力扣（LeetCode）

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];
    }
};