Simple 8 lines of C++ codes, O(logn) time, O(1) space.


  • 0
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        while (l<r) {
            int m = (l+r)/2;
            if (nums[m]<nums[r]) r=m;
            else if (nums[m]>nums[r]) l=m+1;
            else r--;
        }
        return nums[l];
    }

  • 0
    K

    the complexity of this solution i O(N), fe if the input is [1,1,1,.....,1,1] (all the sam for let say 1bn times) You need 1bn iterations of main loop.


  • 0
    E
    This post is deleted!

Log in to reply
 

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