154.尋找旋轉排序數組中的最小值II c++實作 3種方法

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

1. 集合法-Set

1. 思路就是直接把這個數組放到集合裡管它是不是重複，直接輸出set第一個值即可，知道這樣會導緻時間複雜度和空間複雜度都比較高就是随便複習下集合的操作哈哈。

class Solution {
public:
    int findMin(vector<int>& nums) {
        set<int>ans={};//
        int n=nums.size()-1;
        for(int i=0;i<=n;i++)
        ans.insert(nums[i]);//将數組插入集合中去
        return *ans.begin();//注意此處疊代器的解引用
    }
};
           

2.直接搜尋

1.思路就是找到第一個數比之前一個數小的那個數，然後輸出即可，這樣比上一個好了一點點，基本複雜度差不多

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n=nums.size()-2;
        for(int i=0;i<=n;i++)
        {
            int j=i+1;
            if(nums[i]>nums[j]) 
            {
               return nums[j]; break; 
            }
        }
        return nums[0];//注意定義一個變量一定要先初始化
    }
};
           

3.二分法搜尋

1. 思路就是利用二分法來去求，二分法就是不斷縮小搜尋的區間範圍，大緻分以下幾種情況
   1. 首先定義三個變量l，r，m，分别代表左端，右端，和中間位置。
   2. 判斷一下l和r的大小關系，此處m=floor((l+r)/2)，如果是左小于右，那麼這個區間不存在最小值，因為是上升的，是以一定在右側區間，将中間值賦給左端，繼續判斷
   3. 然後特殊情況就是發現左右相等，把左右的一端縮小範圍，，這一步相當于順序查找了。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l=0,r=nums.size()-1,m=0;
        if (r==0) return nums[0];
        while(r-l!=1)//
        {   
            m=(int)(l+r)/2;
            
            if(nums[l]<nums[m]&&nums[m]<nums[r])
                return nums[l];//如果是沒有旋轉寫的有點備援
                
            if(nums[r]==nums[l])
                r--;
            else if(nums[m]>nums[r]||nums[l]==nums[m])
                l=m;
            else if(nums[l]>nums[m]||nums[m]==nums[r])
                r=m;//小bug太多都得用例子，沒法實作bug free ，需要思考小
        }
        if(nums[l]<nums[r])
            return  nums[l];
        else if(nums[l]>=nums[r])
            return  nums[r];
        else
            return 0;
    }
};
           

1. 參考一下别人的代碼，這個也作為我以後遇到2分法類似題目的模版

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        if(nums[0] < nums[r])  return nums[0];//一行簡單明了判斷是否旋轉了
        while(l + 1 < r){//這裡不用l<r，否則會導緻死循環
            int mid = l + (r - l)/2;//這裡等價于mid=（l+r）/2我選擇這個
            if(nums[mid] < nums[r])    r = mid;
            else if(nums[mid] > nums[r])   l = mid;
            else{
                -- r;//這裡的--r，是精華縮小了界限
            }
        }
        return nums[r];//目的就是要找到那個旋轉的數組，是以一定是後面的小
    }
};
           

知識點及反思

1. 第一次學習二分法，其實還是應該這種先看答案，沒必要自己做，因為有些細節第一次可能想的很慢，是以導緻bug太多，下次類似情況先看代碼，二分法這種應該總結一個模版，友善下次進行使用