My C++ solution, 11ms


  • 0
    Z
    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int n=nums.size();
            if(n==1) return nums[0];
            if(nums[n-1]<nums[n-2]) return nums[n-1];//deal with the case that the smallest number is at the end
            int min=nums[0];//deal with the case that the smallest number is the first number
            
            int left=0,right=n-1;
            int pos=-1;
            int pos2=(left+right)/2;
            
            while(pos!=pos2){
                pos=pos2;
                if(nums[pos]>nums[pos+1]) return nums[pos+1];//because have dealt with the special case, it is safe to write this   
                if(nums[pos]<nums[pos-1]) return nums[pos];
                
                if(nums[pos]>nums[left])
                    left=pos;
                else if(nums[pos]==nums[left]){//because of this search, the complexity can be O(n) instead of O(logn)
                    int temp=pos;
                    while(nums[temp]==nums[left] && temp>left){
                        temp--;
                    }
                    if(temp==left)
                    left=pos;
                    else
                    right=pos;
                }
                else{
                    if(nums[pos]>=nums[pos-1])
                    right=pos;
                }
                pos2=(left+right)/2;
            }
            if(min>nums[pos])
            return nums[pos];
            return min;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.