Find Minimum in Rotated Sorted Array--LeetCode

旧城等待， 2022-08-07 12:57 12阅读 0赞

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., `0 1 2 4 5 6 7` might become `4 5 6 7 0 1 2`).

Find the minimum element.

You may assume no duplicate exists in the array.

思路：里面肯定有一个是单调的子序列，和很早的查找有相似之处。

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    int FindMin(vector<int>& vec)
    {
        int low=0,high = vec.size()-1;
        int mid,minnum;
        minnum = vec[0];
        while(low<= high)
        {
          mid = low+ (high-low)/2;
          cout<<mid<<endl;
          if(high-1 == low)
           minnum = min(minnum,min(vec[low],vec[high]));
          if(vec[low] < vec[mid]) // 升序
          {
              minnum = min(minnum,vec[low]);
              low = mid+1;       
          }                
          else if(vec[mid] < vec[high])
          {
             minnum = min(minnum,vec[mid]);
             high = mid-1;    
          }     
          else
             return min(minnum,vec[high]);     //说明完全翻转了
        } 
        return minnum;
    }
    int main()
    {
        int array[] = {9,8,7,6,5,4,3,2,1};
        vector<int> vec(array,array+sizeof(array)/sizeof(array[0]));
        cout<<FindMin(vec);
        system("pause"); 
        return 0;
        }

ps:题目中已经说明，不会出现重复的元素出现，经过旋转以后，在这个数组中肯定有一段空间是单调的，我们锁定那块单调的空间，然后再比较单调空间的最小值，然后再不单点的空间中查找即可。如果没有发现单调的空间，那么这个这个数组肯定发生了全旋转