# Untitled

a guest
Oct 1st, 2021
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution {
2. public:
3.     void nextPermutation(vector<int>& num) {
4.
5.        // next_permutation(nums.begin(), nums.end());
6.
7.         if (num.size() < 2) return;
8.
9.         // in reverse order, find the first number which is in increasing trend (we call it violated number here)
10.         int i;
11.         for (i = num.size()-2; i >= 0; --i)
12.         {
13.             if (num[i] < num[i+1]) break;
14.         }
15.
16.         // reverse all the numbers after violated number
17.         reverse(begin(num)+i+1, end(num));
18.         // if violated number not found, because we have reversed the whole array, then we are done!
19.         if (i == -1) return;
20.         // else binary search find the first number larger than the violated number
21.         auto itr = upper_bound(begin(num)+i+1, end(num), num[i]);
22.
23.         swap(num[i], *itr);
24.     }
25. };