下一个排列
题目
整数数组的一个排列就是将其所有成员以序列或线性顺序排列.
例如, 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.length <= 100
0 <= nums[i] <= 100
示例
输入: nums = [1, 2, 3]
输出: [1, 3, 2]
输入: nums = [3, 2, 1]
输出: [1, 2, 3]
输入: nums = [1, 1, 5]
输出: [1, 5, 1]
题解
这道题的目的是寻找下一个比它大的最近接的那个值, 我们用 13481
这个数字来演示:
- 首先从十位看起, 也就是
81
, 它已经是十位数里面最大的了, 这个已经无法更换了 - 因此继续看百位, 即
481
, 比它更大且只能用本身的数字那就是841
, 我们需要将4
和8
互换位置 - 但我们发现, 它其实不是最小的, 还有一个位置可以更小, 那就是
1
跟4
再做一次升序, 即把数字变成814
- 因此一次的转换后, 从
13481
的下一个数就是13814
, 在这个过程里, 就涉及到了三个过程
总结来看:
- 第一个过程寻找替换计数单位的下标, 也就是
4
- 第二个过程