Leetcode Find Minimum in Rotated Sorted Array 题解

Leetcode Find Minimum in Rotated Sorted Array

题目大意：

     对一个有序数组翻转， 就是随机取前K个数，移动到数组的后面，然后让你找出最小的那个数，注意，K有可能是0，也就是没有翻转。

     毫无疑问，遍历一次肯定可以找到，但这样时间复杂度是O(n)，如果你在面试的时候遇到这样的问题，你这样回答面试官肯定不会满意的，我们接下来讨论有没有什么更快的方法。O(nlogn)??

我还是把O(N)的代码贴出来，不知道为什么leetcode上居然不超时。

  

   

    

     

    
    

     

      //O(n)
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    int findMin(vector<int> &num) {
     
    
   

    

     

    
    

     
        int minval = 0x3f3f3f3f;
     
    
   

    

     

    
    

     
        int len = num.size();
     
    
   

    

     

    
    

     
        for (int i = 0; i < len; i++) {
     
    
   

    

     

    
    

     

                  minval = min(minval, num[i]);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return minval;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

       我本人写了两次代码，第一份很不尽人意，首先对没有翻转的情况做了特判，然后一直遇到二分边界的问题，只要二分两个数的时候就会死循环，索性就加了特判，两个数的时候直接输出最小的一个，代码冗长混乱，思路也不严谨，先贴出来做个反例。

  

   

    

     

    
    

     

      //O(nlogn) bad
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    int findMin(vector<int> &num) {
     
    
   

    

     

    
    

     
        int len = num.size();
     
    
   

    

     

    
    

     
        if (num[0] <= num[len-1])
     
    
   

    

     

    
    

     
            return num[0];
     
    
   

    

     

    
    

     
        int l = 0, r = len-1;
     
    
   

    

     

    
    

     
        while (l < r) {
     
    
   

    

     

    
    

     
            int mid = (l+r)>>1;
     
    
   

    

     

    
    

     
            if (num[mid] > num[l]) {
     
    
   

    

     

    
    

     
                if (num[mid] > num[0])
     
    
   

    

     

    
    

     

                          l = mid+1;
     
    
   

    

     

    
    

     
                if (num[mid] < num[len-1])
     
    
   

    

     

    
    

     

                          r = mid;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     
            else if (num[mid] < num[r])
     
    
   

    

     

    
    

     

                      r = mid;
     
    
   

    

     

    
    

     
            else 
     
    
   

    

     

    
    

     
                return min(num[l], num[r]);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return num[l];
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

  

   

    

     

    
    

     

      //O(nlogn) good 
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    int findMin(vector<int> &num) {
     
    
   

    

     

    
    

     
        int len = num.size();
     
    
   

    

     

    
    

     
        int l = 0, r = len-1;
     
    
   

    

     

    
    

     
        while (l < r) {
     
    
   

    

     

    
    

     
            int mid = (l+r)>>1;
     
    
   

    

     

    
    

     
            if (num[mid] > num[r])
     
    
   

    

     

    
    

     

                      l = mid+1;
     
    
   

    

     

    
    

     
            else 
     
    
   

    

     

    
    

     

                      r = mid;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return num[l];
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/40370675