首页 > 代码库 > Next Permutation[leetcode]
Next Permutation[leetcode]
基本思路是从后往前找到第一个递减的数num[index],并与之前的第一个大于num[index]的数交换位置。
注意交换后[index+1...n-1]仍是非递减的,所以只需要reverse一下,使其变成非递增的
void nextPermutation(vector<int> &num) { int index = num.size() - 2; int rIndex = index; //traverse forward till find first decending num, save in index for (; index >= 0; index--) { //find first num larger than nun[index], save in rIndex if (num[index + 1] > num[index]) { for (rIndex = num.size() - 1; rIndex > index && num[index] >= num[rIndex]; rIndex--); swap(*(num.begin() + index), *(num.begin() + rIndex)); break; } } reverse(num.begin() + index + 1, num.end());//do not need sort, just reverse }
Next Permutation[leetcode]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。