tint-k主题做企业网站,做ppt的软件模板下载网站,主机屋 大网站,专业的购物网站定制这道题本来想直接暴力回溯的#xff0c;但是想了下还是算了#xff0c;自己想这个思路完全想不出来#xff0c;直接去看灵神的题解了#xff0c;感觉还是很好懂的#xff0c;强烈推荐去看看他的题解。 我们先讨论最一般的情况#xff1a;对于一组排列#xff0c;我们要找… 这道题本来想直接暴力回溯的但是想了下还是算了自己想这个思路完全想不出来直接去看灵神的题解了感觉还是很好懂的强烈推荐去看看他的题解。 我们先讨论最一般的情况对于一组排列我们要找到它的下一个排列就需要从右往左遍历找到第一个小于右边相邻元素的位置。例如对于排列[3, 5, 1, 4, 2, 6, 1]我们要找下一个大于当前数的排列(nums[i] nums[i 1])我们就需要找到元素2的位置i它是从右往左数第一个小于右边相邻元素的数此时我们还不能简单地将2和6简单交换位置就草草了事因为如果输入是[3, 5, 1, 4, 2, 6, 0]将2和6交换位置将得到[3, 5, 1, 4, 6, 2, 0]显然下一个排列应当为[3, 5, 1, 4, 6, 0, 2]。因此在找到i之后我们可以得到如下性质从i 1到数组的最后一个元素这段数字应当是降序排列的这是因为i是从右往左数第一个小于右侧相邻元素的值从i 1到数组的倒数第二个元素每一个元素都大于等于右边相邻的元素从而形成降序排列。我们还需要寻找一个元素nums[j],使得nums[j]恰好为大于nums[i]的元素中的最小值从右往左数第一个大于nums[i]的元素就是nums[j],对于输入[3, 5, 1, 4, 2, 6, 0]nums[i] 2nums[j] 6我们将其位置交换得到[3, 5, 1, 4, 6, 2, 0]。此时还没有得到下一个排列因为[i 1, end)这个区间是降序排列的我们仍需要对其进行逆转为升序排列使其变得更小最终得到下一个排列因此我们通过reverse(nums.begin() i 1, nums.end());来实现反转从而得到下一个排列。 下面再来讨论特殊情况当原排列已经是最大的排列不可能得到更大的排列时我们需要将其转化为最小的排列最大的排列一定是从头到尾都降序排列我们将其逆转得到升序排列此时一定是最小的排列。 综上所述如果我们能找到符合条件的i那么我们还需要进行第二步操作找到符合条件的j进行交换如果找不到就直接执行第三步操作。第三步将指定范围内的排列逆序。最终得到下一个排列。
class Solution {
public:void nextPermutation(vectorint nums) {int n nums.size();//1.从右往左寻找第一个小于右侧相邻元素的数int i n - 2;while(i 0 nums[i] nums[i 1])i--;//2.如果找到了那么一定满足i 0,如果不满足则跳过第2步//此时从i 1到末尾一定是单调递减的因为i是从右往左数第一个小于右侧相邻元素的值if(i 0){int j n - 1;while(nums[j] nums[i])j--;swap(nums[i], nums[j]); //交换i和j的位置数值已经变大但是可能不是最接近原数的下一个排列}//3.如果存在对应的i则此阶段需要进行最后的微调由于[i 1, end)这个区间是降序排列的//我们仍需要对其进行逆转为升序排列使其变得更小//如果没有找到合适的i则说明原来的排列已经是最大值我们需要将其逆序排列得到最小值reverse(nums.begin() i 1, nums.end());}
};
