Advertisement
Guest User

Untitled

a guest
Oct 1st, 2021
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  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. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement