首页 > 代码库 > Leetcode#31 Next Permutation
Leetcode#31 Next Permutation
原题地址
生成字典序，交换 + 逆序
生成字典序的方法：
1. 从后向前，寻找第一个正序对，即num[i] < num[i+1]
2. 从后向前，寻找第一个大于num[i]的数字，即num[i]<num[j]
3. 交换num[i]和num[j]
4. 将num[i+1...]转为逆序
如果第1步找不到这样一个i，说明已经是字典序的最后一个序列了，此时将数字恢复成第一序列，即从小到大排序。
代码：
1 void nextPermutation(vector<int> &num) { 2 int i = num.size() - 2; 3 while (i >= 0 && num[i] >= num[i + 1]) 4 i--; 5 6 if (i < 0) { 7 sort(num.begin(), num.end()); 8 return; 9 }10 11 int j = num.size() - 1;12 while (j > i && num[j] <= num[i])13 j--;14 15 swap(num[i], num[j]);16 sort(num.begin() + i + 1, num.end(), [](int &a, int &b) {return b - a;});17 }
Leetcode#31 Next Permutation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。