My C++ solution 20ms is there any better solution ?


  • 0
    S

    // Assumption : the array is sorted in increasing order and then rotated

    // GAYLE LAAKMANN APPROACH - Cracking the coding interview

    class Solution {
    public:
        int findMin(vector<int> &num) {   
    
            int left = 0;
            int right = num.size() - 1;
            
            int m = num[0];
            while(left <= right){
            	if(left == right) return min(m, num[left]);
    
                int mid = (left + right)/2;
    
                if(num[left] < num[mid]){ // Left is normally ordered            	
                    m = min(m, num[left]);
                    if(mid+1 > right) return m;
                    left = mid+1;
                }
                else if(num[mid] < num[left]){ // Right is normally ordered
                    m = min(m, num[mid]);
                    if(mid <= left) return m;
                    right = mid;
                }
                else{
                	// now we have ->  num[left] == num[mid] 
                	if(num[mid] != num[right]) {
                		m = min(m, num[mid]);
                		if(mid+1 > right) return m;
                		left = mid+1;
    
                	}
                    else left++;
                }
            }
        }
    };

Log in to reply
 

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