Straight-Forward C++ Solution with Comparison with problem 153 (12ms)


  • 0
    K

    This solution is an improvement of Problem 153 with consideration of existed duplicates. The only thing we need to add is to determine which part(left or right) should we choose when middle value is the same as last value. The code is shown below:

    The first code segment is for problem 153 which do NOT have duplicates:

    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int start=0;
            int end=nums.size()-1;
            while(start<end){
                if(start==(end-1)) return nums[start]>nums[end]?nums[end]:nums[start];
                int mid=(start+end)/2;
                if(nums[mid]>nums[end]) start=mid;
                else end=mid;
            }
            return nums[start];
        }
    };
    

    The second code segment is for this problem which has duplicates:

    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int start=0;
            int end=nums.size()-1;
            while(start<end){
                if(start==(end-1)) return nums[start]>nums[end]?nums[end]:nums[start]; 
                int mid=(start+end)/2;
                if(nums[mid]<nums[end]) end=mid;
                else if(nums[mid]>nums[end]) start=mid;
                else if(nums[mid]==nums[end]){
                    for(int i=0;i<mid;i++){
                        if(nums[i]!=nums[mid]) end=mid;
                    }
                    if(end!=mid) start=mid;
                }
            }
            return nums[start];
        }
    };

Log in to reply
 

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