下一个排列 的 思路总结

• 思路分析：
  • 倒序遍历：题目要求的是下一个排列，那么肯定数字的跳跃不能太大，所以可以比较好确定的是，遍历的顺序是倒序遍历
  • 比较方向：对于每一个数字，需要找到右边最大的比它小的数字，然后交换之后，剩余的数字进行升序排序

灵神题解

class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();// 第一步：从右向左找到第一个小于右侧相邻数字的数 nums[i]int i = n - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}// 如果找到了，进入第二步；否则跳过第二步，反转整个数组if (i >= 0) {// 第二步：从右向左找到 nums[i] 右边最小的大于 nums[i] 的数 nums[j]int j = n - 1;while (nums[j] <= nums[i]) {j--;}// 交换 nums[i] 和 nums[j]swap(nums[i], nums[j]);}// 第三步：反转 [i+1, n-1]（如果上面跳过第二步，此时 i = -1）reverse(nums.begin() + i + 1, nums.end());}
};

错误代码示例：

• 我开始写的思路是，倒序遍历的思路没问题，但是找到合适的交换对象的时候，我找的是每一个数字左边第一个比它小的数字，然后交换的位置的右边再进行升序排列

• 错误分析：下一个排列，应该是尽量操作右边的数字，并且我们是倒序遍历的，所以遍历过的部分的情况可以知道，所以寻找的交换顺序的时候，还是往右边进行考虑