题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如,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] <= 100
题目解释
这道题题目描述可能没那么容易直观理解,这里给大家简要解释一下,我们可以把数组直接理解为一个整数。例如:[1, 2, 3]
直接理解为数字123,然后下一个排列就是找由1,2,3排列后组成的比123大的数,如题所述,下一个排列的数是132,可能有的同学就有疑问了,还有213、231也比123大,也是由1,2,3排列组成的,所以这就是这个题目不太好理解的地方,这个数必须是刚好比123大如果是213,那么中间就还有132,所以213不符合排列要求。同理132的下一个只能是213,而到了最后321是1,2,3能排列组合的最大数了,此时其下一个排列就是1,2,3排列组合的最小数,因此[3, 2, 1]
的下一个排列是[1, 2, 3]
代码及注释
func nextPermutation(nums []int) {
n := len(nums)
i := n - 2
// 1. 从右往左找到第一个破坏递增序列的数字
for i >= 0 && nums[i] >= nums[i + 1] {
i--
}
// 如果找不到这样的数字,说明当前排列是字典序最大的,直接将数组逆序即可
if i >= 0 {
j := n - 1
// 2. 从右往左找到第一个大于 nums[i] 的数字
for j >= 0 && nums[j] <= nums[i] {
j--
}
// 3. 交换 nums[i] 和 nums[j]
nums[i], nums[j] = nums[j], nums[i]
}
// 4. 将 nums[i+1:] 逆序
reverse(nums[i + 1:])
}
func reverse(nums []int) {
left, right := 0, len(nums) - 1
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
代码解释
步骤1:找到第一个不是升序的数字
从右向左遍历数组,找到第一个违反升序的数字的索引i
。如果整个数组是降序排列的,那么i
的值会是-1
。
例如,对于数组[1, 3, 5, 4, 2]
,i
的值为1
,因为3
比5
小。
步骤2:找到第一个比nums[i]
大的数字
在i
的右侧,从右向左遍历数组,找到第一个比nums[i]
大的数字的索引j
。
例如,在数组[1, 3, 5, 4, 2]
中,j
的值为3
,因为4
比3
大。
步骤3:交换nums[i]
和nums[j]
交换nums[i]
和nums[j]
。
例如,在数组[1, 3, 5, 4, 2]
中,交换nums[1]
和nums[3]
得到[1, 4, 5, 3, 2]
。
步骤4:反转i
后面的所有数字
由于i
后面的数字是降序排列的,所以为了得到字典序中的下一个排列,需要反转i
后面的数字。
例如,在数组[1, 4, 5, 3, 2]
中,反转i=1
后面的数字得到[1, 4, 2, 3, 5]
。
例子
-
对于数组
[1, 3, 5, 4, 2]
:i = 1
j = 3
- 交换
nums[1]
和nums[3]
得到[1, 4, 5, 3, 2]
- 反转
i=1
后面的数字得到[1, 4, 2, 3, 5]
-
对于数组
[3, 2, 1]
:i = -1
- 反转整个数组得到
[1, 2, 3]
这样就可以原地修改数组得到下一个排列了。