Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3
→ 1,3,2
3,2,1
→ 1,2,3
1,1,5
→ 1,5,1
思路:
题目意思是找出一个比给定数组大的组合中最小的一个组合,比如比123大的组合当中最小的就是132,题目要求在原数组中操作,常数的空间复杂度,所以只能通过交换原数组的方式来实现。
1 2 3 4 5
翻转为5 4 3 2 1
。代码:
go:
func nextPermutation(nums []int) {
if nums == nil || len(nums) == 0 {
return
}
size := len(nums)
start := size - 2
// 从后往前找,找到第一个比后一个小的位置
for start >= 0 && nums[start] >= nums[start + 1] {
start--
}
// 如果这个数不是递减,说明,需要和后面的第一个比他大的做一个调换
if start >= 0 {
// 找到第一个比当前数小的进行交换
k := size -1
for ; k > start && nums[k] <= nums[start]; {
k--
}
nums[k], nums[start] = nums[start], nums[k]
}
// 这时候从start+1到数组结束是一个严格递减的数组,只用翻转一下,就会变成一个严格递增,也就是最小的数
for i, j := start + 1, size - 1; i < j; {
nums[i], nums[j] = nums[j], nums[i]
i++
j--
}
}