Leetcode筆記目錄

154. 尋找旋轉排序數組中的最小值 II hard

• Leetcode筆記目錄
• 一、題目描述
• 二、解題過程
• • 1.思想
  • 2.代碼
• 三、總結

一、題目描述

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。

請找出其中最小的元素。

注意數組中可能存在重複的元素，且數組不一定進行了旋轉。

示例1：

• 輸入: [1,3,5]

  輸出: 1

示例2：

• 輸入: [2,2,2,0,1]

  輸出: 0

二、解題過程

1.思想

與Leetcode33，81同是旋轉數組題目，本題充分利用了旋轉數組的特性(在斷點處左右分為兩個有序序列，且左邊的值一定大于右邊)，本題即為用二分法尋找旋轉數組的斷點(如果旋轉了的話)：

• 本題的特性适合使用左閉右開，因為不是尋找值為target的項，而是找到最後得到left=right的單元素數組，邏輯為不斷比較端點和mid的值縮小斷點的區間直到縮到單元素數組，使用左右端點皆可，但右端點比較合适；
• 以右端點為例比較：若nums[mid]>nums[right]，則斷點定在[mid+1,right]，否則的話，斷點定在[left,mid]，若相等，則right-1。
• 若以左端點比較，則需要多兩個判斷，即左端點比較無法處理無旋轉數組和left剛好是斷點的情況(此時left會+1)。

2.代碼

左端點版本：

int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        if (nums[left] < nums[right]) {  //無旋轉數組單獨處理
            return nums[left];
        }
        while (left < right) {
            int mid = left + (right-left) / 2;
            if (left > 0 && nums[left] < nums[left - 1]) {   //left剛好是斷點單獨處理
                return nums[left];
            }
            if (nums[left]<nums[mid]) {
                left = mid + 1;
            } else if (nums[left]>nums[mid]) {
                right = mid;
            } else {
                left++;
            }
        }
        return nums[left];
    }
           

右端點版本：

int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right-left) / 2;
            if (nums[right]<nums[mid]) {
                left = mid + 1;
            } else if (nums[right]>nums[mid]) {
                right = mid;
            } else {
                right--;
            }
        }
        return nums[left];
    }
           

三、總結

不是有序數組不能套模闆，邊界需要很小心的讨論。