A 4 ms C++ solution


  • 0
    int find(vector<int>& n, int le, int ri)
    {
    	if (le >= ri)
    		return n[le];
    	int m = le + (ri - le) / 2;
    	if (n[le] <= n[ri] && n[le]<=n[m])
    		return n[le];
    	if (n[m] >= n[le])
    		find(n, m + 1, ri);
    	else
    		find(n, le, m);
    }
    int findMin(vector<int>& ns) 
    {
    	return find(ns, 0, ns.size() - 1);
    }
    

    This solution is no longer useful when duplicates are allowed. Because when case is 2 2 2 1 2 or 2 1 2 2 2,
    we can not determine smallest number '1' is in the first half or second half of array.


Log in to reply
 

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