My solution, take the array as a circle(c++)


  • 0
    D

    Just take the array as a circle array.The first element of the array is a random point of the circle.The minimum element is another point of the circle.From one point to another point in the circle, there are major arc and minor arc. Obviously the minor one is what we wanted. So I traverse the array in 2 directions(forward & backward) at the same time.

    class Solution {
    public:
    	int findMin(vector<int> &num) {
    		if (num.size() == 1)
    			return num[0];
    		vector<int>::const_iterator iter = num.begin();
    		vector<int>::const_reverse_iterator riter = num.rbegin();
    		int ipre = *riter;
    		int ripre = *iter;
    		if (*iter < ipre)
    			return *iter;
    		ipre = *iter;
    		iter++;
    		while (true){
    			if (*iter < ipre)
    				return *iter;
    			ipre = *iter;
    			iter++;
    			if (*riter > ripre)
    				return ripre;
    			ripre = *riter;
    			riter++;
    			if (iter == num.end() || riter == num.rend()){
    				return num[0];
    			}
    		}
    
    	}
    };

Log in to reply
 

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