在电脑上怎么建设网站,中国建筑设计作品网站,中国互联网协会会员,商业网线多少钱一年1. 题目
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如#xff0c;arr [1,2,3] #xff0c;以下这些都可以视作 arr 的排列#xff1a;[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地arr [1,2,3] 以下这些都可以视作 arr 的排列[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地如果数组的所有排列根据其字典顺序从小到大排列在一个容器中那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列那么这个数组必须重排为字典序最小的排列即其元素按升序排列。
例如arr [1,2,3] 的下一个排列是 [1,3,2] 。 类似地arr [2,3,1] 的下一个排列是 [3,1,2] 。 而 arr [3,2,1] 的下一个排列是 [1,2,3] 因为 [3,2,1] 不存在一个字典序更大的排列。 给你一个整数数组 nums 找出 nums 的下一个排列。
必须 原地 修改只允许使用额外常数空间。
示例 1
输入nums [1,2,3]
输出[1,3,2]示例 2
输入nums [3,2,1]
输出[1,2,3]示例 3
输入nums [1,1,5]
输出[1,5,1]提示
1 nums.length 100
0 nums[i] 1002. 解题思路
我们可以将该问题形式化地描述为给定若干个数字将其组合为一个整数。如何将这些数字重新排列以得到下一个更大的整数。如 123 下一个更大的数为 132。如果没有更大的整数则输出最小的整数。
那么就应该尽量少动前面的数因为前面的数是高位尽量动后面的低位数
分析过程
具体怎么动呢? 只需要 将后面的「大数」与前面的「小数」交换就能得到一个更大的数。比如 123456将 5 和 6 交换就能得到一个更大的数 123465。 我们还希望下一个数 增加的幅度尽可能的小比如 123465下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换 将「大数」换到前面后需要将「大数」后面的所有数 重置为升序升序排列就是最小的排列。以 123465 为例首先按照上一步交换 5 和 4得到 123564然后需要将 5 之后的数重置为升序得到 123546。显然 123546 比 123564 更小;
实现过程
从后向前 查找第一个 相邻升序 的元素对(i,j)满足 A[i] A[j]。此时 [j,end) 必然是降序在 [j,end) 从后向前 查找第一个满足 A[i] A[k] 的 k。将 A[i] 与 A[k] 交换可以断定这时 [j,end)必然是降序逆置 [j,end)使其升序如果在步骤 1 找不到符合的相邻元素对说明当前 [begin,end) 为一个降序顺序则直接跳到步骤 4
3. C代码
class Solution {
public:void nextPermutation(vectorint nums) {int n nums.size();for (int in-2; i0; i--){int j i1;if (nums[j] nums[i]){for (int kn-1; kj; k--){if (nums[k] nums[i]){swap(nums[i], nums[k]);reverse(nums.begin()j, nums.end());return;}}}}reverse(nums.begin(), nums.end());return;}
};
