[LeetCode]31. Next Permutation

题目描述

思路

开始的思路：找到最靠右的 nums[i -1]小于nums[i]，并在nums[i]的右边找出小于nums[i]并且大于nums[i - 1]的数，将此数与nums[i]交换，之后递归，这个思路会导致一些比较简单的情况无法出来 后续： 例：

数组142321index012345

找到不满足逆序排列的第一个数

数组142321index012(i)3(flag)45

然后将逆序排列的数倒序

数组142123index012(i)3(flag)45

之后找出逆序后的数中的最大值

数组142123index012(i)3(flag)45(max)

将max与i位置的数交换

数组143122index012(i)3(flag)45(max)

即得最终结果

代码

class Solution { public: void nextPermutation(vector<int> &num) { if (num.empty()) return; int i; for (i = num.size()-2; i >= 0; --i) { if (num[i] < num[i+1]) break; } reverse(begin(num)+i+1, end(num)); if (i == -1) return; auto itr = upper_bound(begin(num)+i+1, end(num), num[i]); swap(num[i], *itr); } };