C++ (26ms) O(n) algorithm


  • 0
    G

    It is easy to find that the tail of the vector is the key to this problem, so we can just do a reverse search when the sequence is increased from end to begin. Then swap the element which interrupt the order.

    class Solution {
    public:
    	void nextPermutation(vector<int>& nums) {
    		int vectorlen = nums.size();
    		if(vectorlen <= 1) return;
    		int tempNum = nums[vectorlen - 1];
    		if(tempNum > nums[vectorlen - 2]){
    			eleSwap(nums,vectorlen - 2,vectorlen - 1);
    			return;
    		}
    		for(int i = vectorlen - 2;i >= 0;i--){
    			if(nums[i] >= tempNum){
    				tempNum = nums[i];
    				continue;
    			}else{
    				int s = i + 1,e = vectorlen - 1;
    				while(s < e - 1){
    					int mid = (s + e) / 2;
    					if(nums[i] >= nums[mid]) e = mid - 1;
    					else if(nums[i] < nums[mid]) s = mid;
    				}
    				if(nums[e] > nums[i]) eleSwap(nums,i,e);
    				else eleSwap(nums,i,s);
    				eleReverse(nums,i + 1,vectorlen - 1);
    				return;
    			}
    		}
    		eleReverse(nums,0,vectorlen - 1);
    		return;
    	}
    private:
    	void eleSwap(vector<int>& nums,int beginPos,int endPos){
    		nums[beginPos] = nums[beginPos] ^ nums[endPos];nums[endPos] = nums[beginPos] ^ nums[endPos];nums[beginPos] = nums[beginPos] ^ nums[endPos];
    		return;
    	}
    	void eleReverse(vector<int>& nums,int beginPos,int endPos){
    		while(beginPos < endPos){
    			eleSwap(nums,beginPos,endPos);
    			beginPos++;endPos--;
    		}
    		return;
    	}
    };
    

Log in to reply
 

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