很明显,对于一个排列而言,最后一个位置是动不了的
那么就从倒数第二个位置开始
用递归一点点分析错了几次之后终于自己写出来了(叉腰骄傲)
void nextPermutation(vector<int>& nums) {
int len = nums.size();
if (len <2) return;
// first保存数字,second保存索引
pair<int, int> minBigger(INT_MAX,-1);
// 从倒数第二个位置开始找向前找
for (int i = len - 2; i >= 0; i--) {
// 从后面的位置中找到一个大于自己且最小的数字
for (int j = i + 1; j < len; j++)
if (nums[j] > nums[i] && nums[j] < minBigger.first) minBigger = { nums[j],j };
if (minBigger.second != -1) {
swap(nums[i], nums[minBigger.second]);
sort(nums.begin() + i + 1, nums.end());
return;
}
}
sort(nums.begin(), nums.end());
}
符合题意,原地修改,常数额外空间
但是,很明显,双重循环理论上来说时间复杂度不会很好看
这里可以加一个剪枝
// i+1位置必然是后面序列中的最大元素
if (nums[i + 1] <= nums[i]) continue;
else minBigger = { nums[i + 1],i + 1 };
for (int j = i + 2; j < len; j++) {}
按理来说应该是有优化的…只是我看不出提交有什么效果……
void nextPermutation(vector<int>& nums) {
int len = nums.size();
if (len <2) return;
// first保存数字,second保存索引
pair<int, int> minBigger;
// 从倒数第二个位置开始找向前找
for (int i = len - 2; i >= 0; i--) {
// 从后面的位置中找到一个大于自己且最小的数字
// i+1位置必然是后面序列中的最大元素
if (nums[i + 1] <= nums[i]) continue;
else minBigger = { nums[i + 1],i + 1 };
for (int j = i + 2; j < len; j++)
if (nums[j] > nums[i] && nums[j] < minBigger.first) minBigger = { nums[j],j };
if (minBigger.second != -1) {
swap(nums[i], nums[minBigger.second]);
sort(nums.begin() + i + 1, nums.end());
return;
}
}
sort(nums.begin(), nums.end());
}
标签:排列,end,nums,int,31,len,力扣,second,minBigger
From: https://www.cnblogs.com/yaocy/p/16978948.html