31.M 下一个排列

Problem: 31. 下一个排列

[TOC]

思路

两遍扫描：

1. 从后往前找到第一个升序对[i, i+1]

2. 从后往前找到第一个大于i的数j

3. 交换i和j位置的数字

4. 反转从i+1到数组末尾的区间

对于找不到升序对的情况，程序就会把整个数组反转。

Code

func nextPermutation(nums []int) {
	if len(nums) <= 1 {
		return
	}

	// 从后往前找到第一个升序对
	i := len(nums) - 2
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}

	if i >= 0 {
		j := len(nums) - 1
		// 从后往前找到第一个大于i的数
		for j > i && nums[j] <= nums[i] {
			j--
		}
		// 交换i和j
		nums[i], nums[j] = nums[j], nums[i]
	}

	// 交换整个数组
	swap(nums[i+1:])
}

func swap(nums []int) {
	i, j := 0, len(nums)-1
	for i < j {
		nums[i], nums[j] = nums[j], nums[i]
		i++
		j--
	}
}