diff options
Diffstat (limited to 'other/next_permutation.cpp')
-rw-r--r-- | other/next_permutation.cpp | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/other/next_permutation.cpp b/other/next_permutation.cpp new file mode 100644 index 0000000..95e70f4 --- /dev/null +++ b/other/next_permutation.cpp @@ -0,0 +1,37 @@ +#include <bits/stdc++.h> +#include <vector> +using namespace std; + +class Solution { +public: + void nextPermutation(vector<int> &nums) { + int i = nums.size() - 2; + while (i >= 0 && nums[i + 1] <= nums[i]) + i--; + if (i >= 0) { + int j = nums.size() - 1; + while (nums[j] <= nums[i]) + j--; + swap(nums, i, j); + } + reverse(nums, i + 1); + } + +private: + void reverse(vector<int> &nums, int start) { + int i = start, j = nums.size() - 1; + while (i < j) { + swap(nums, i, j); + i++; + j--; + } + } + + void swap(vector<int> &nums, int i, int j) { + int temp = nums[i]; + nums[i] = nums[j]; + nums[j] = temp; + } +}; + +int main() {} |