Simple c++ solution in 8ms


  • 0
    S
    class Solution {
    public:
    int findMin(vector<int> &num) {
    	int b=0, e=num.size();
    	int result = INT_MAX;
    	while(b!=e) {
    		auto mid = (b+e)>>1;
    		if(num[mid]>num[b]) {
    			result = min(num[b],result);
    			b = mid+1;
    		}
    		else if(num[mid]<num[b]) {
    			result = min(num[mid],result);
    			e = mid;
    		}
    		else result = min(num[b++],result);
    	}
    	return result;
    }
    };

  • 1
    E

    so the worst case is O(n) since the last case: result = min(num[b++],result);
    if most of the numbers are duplicates, then this algorithm will go through every element.


Log in to reply
 

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