【c++】【leetcode 31】下一个排列

【【c++】【leetcode 31】下一个排列】
解题思路下一个比当前字典序大的排列有如下特征：（假设为[1,3,2,4]）
1、交换的位次是最靠后的，比如这里交换之后1和3保持不变
2、从小到大排列是字典序最小的
3、从大到小排列是字典序最大的

从后往前找到第一个逆序nums[i] > nums[i - 1] ，即与后面的交换的为nums[i-1]
在后面的n-i个数里，找到与要交换的数最接近的进行交换
交换完成之后，把剩下的逆序改为正序排列，保证交换完之后最小

时间复杂度：最坏的情况下需要遍历三次数组，因此时间复杂度为O(3n)
空间复杂度：O(1)
代码

class Solution {public:void nextPermutation(vector& nums) {int n = nums.size();int i = n - 1;for (; i > 0; i--) {//从后往前遇到的第一个逆序nums[i] > nums[i - 1]if (nums[i] > nums[i - 1]) {for (int j = n - 1; j >= i; j--) {//从后面的i-n个数中 ， 找到第一个比nums[i-1]大的与之交换if (nums[j] > nums[i - 1]) {swap(nums[j], nums[i - 1]);break;}}break;}}//上面交换完成之后 ， 把身下的逆序改为正序for (int j = i, k = 1; j < (n + i) / 2; j++, k++) {swap(nums[n - k], nums[j]);}}};