Concise C++ solution 12ms O(nlgn) solution with detailed explain

• 思路：2次遍历O(n)，从后往前，如果数组不是一路降序，一定可以找到一个位置破坏了排序，这第一个位置就是我们关心的。例如：[2,1,3,5,4,3,2,1,0], 左数第一个3就是从右边数第一个破坏顺序的元素，将之与其右边最靠右的比它大的元素（4）交换，然后再将4之后的元素排序O(nlgn)，就得到了结果。无独有偶，发现我的思路和别人是一样的.

Traverse the array twice backwards using two pointers

First time: to find if the array is in descending order, if yes, reverse the array; otherwise, you can find the first element to the right that breaks the descending order, mark the position of it as turn;

Second time: to find the first element i to the right that's smaller than nums[turn], then swap them, and reorder the elements to the right of position turn.

I found later this idea was well explained here:

https://leetcode.com/submissions/detail/54604251

``````class Solution {
public:
void nextPermutation(vector<int>& nums) {
int turn = -1;
// Search backwards to find the first position 'turn' that breaks the order
// e.g. [4,2,0,2,3,2,0] <-- search backwards
// 0 -> 2 -> 3 -> 2 (found it! 0 < 2 < 3 >2)
for(int i = nums.size() - 1; i > 0; i--){
if(nums[i] > nums[i - 1]) {
turn = i - 1;
break;
}
}
// Search backwards again, find the first element that is larger than nums[turn], then swap
// then sort the array after nums[turn]
int i = nums.size();
while(i--){
// if turn equals it's initial value, means the vector is descending order
if(turn == -1 || nums[turn] < nums[i]){
if(turn >= 0) swap(nums[turn], nums[i]);
sort(nums.begin() + turn + 1, nums.end());
break;
}
}
return;
}
};``````

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