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

• 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;
}
};

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