# Accepted c++ solution, 12ms, as fast as std::next_permutation, easy understand.

• For example, if the permutation is [1,4,6,5,3,2], search from right to left to find the first index which meet
the condition nums[i] < nums[i + 1], we can get nums[1] < nums[2], so idx1 = 1, then search from right to left again to find the first index which meet the condition nums[i] > nums[idx1], we can get nums[3] > nums[1], so idx2 = 3, after swap nums[idx1] and nums[idx2], the permutation is [1,5,6,4,3,2] now, and the sub permutation after idx1 is in descending order, here is [6,4,3,2], we should turn it into ascending order.

``````class Solution {
public:
void nextPermutation(std::vector<int> &nums) {
int len = static_cast<int>(nums.size());
if (len < 2)
return;
int idx1 = -1, idx2;
// search from right to left to find the first index which meet the condition nums[i] < nums[i + 1]
for (int i = len - 2; i >= 0; --i)
if (nums[i] < nums[i + 1]) {
idx1 = i;
break;
}
if (idx1 != -1) {
// search from right to left again to find the first index which meet the condition nums[i] > nums[idx1]
for (int i = len - 1; i != idx1; --i)
if (nums[i] > nums[idx1]) {
idx2 = i;
break;
}
std::swap(nums[idx1], nums[idx2]);
}
// turn the sub permutation after idx1 into ascending order
++idx1;
idx2 = len - 1;
while (idx1 < idx2)
std::swap(nums[idx1++], nums[idx2--]);
}
};
``````

Use STL function std::next_permutation, also 12ms:

``````class Solution {
public:
void nextPermutation(std::vector<int> &nums) {
std::next_permutation(nums.begin(), nums.end());
}
};
``````

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