下一个排列

1. 题目描述

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

2. 思路

1. 思路一
   • 暴力法
   • 先把所有的排列枚举出来
   • 去重排序
   • 找到下一个排列
2. 思路二
   • 后面的大数与前面的小数交换

3. 实现

3.1. 暴力法

package main

import (
	"reflect"
	"sort"
)

func nextPermutation(nums []int)  {
	visited := make(map[int]bool, 0)
	path := make([]int, 0)
	allPaths := make([][]int, 0)
	permuteDFS(nums, 0, &allPaths, &path, visited)

	sort.Slice(allPaths, func(i,j int) bool {
		a := allPaths[i]
		b := allPaths[j]
		for i := 0; i < len(a); i++ {
			if a[i] < b[i] {
				return true
			}else if a[i] == b[i] {
				continue
			}else {
				return false
			}
		}

		return false
	})

	for i, v := range allPaths {
		if reflect.DeepEqual(v, nums) {
			res := allPaths[(i+1) % len(allPaths)]
			for i := 0; i < len(nums); i++ {
				nums[i] = res[i]
			}
			return
		}
	}

	return
}

func exists(path *[]int, allPaths *[][]int) bool {
	for i := 0; i < len(*allPaths); i++ {
		if reflect.DeepEqual((*allPaths)[i], *path) {
			return true
		}
	}

	return false
}


func permuteDFS(nums []int, index int, allPaths *[][]int, path *[]int, visited map[int]bool) {
	if index == len(nums) {
		if exists(path, allPaths) {
			return
		}
		dst := make([]int, len(nums))
		copy(dst, *path)
		*allPaths = append(*allPaths, dst)
		return
	}

	for i := 0; i < len(nums); i++ {
		if visited[i] {
			continue
		}

		visited[i] = true
		*path = append(*path, nums[i])

		permuteDFS(nums, index+1, allPaths, path, visited)

		visited[i] = false
		*path = (*path)[:len(*path)-1]
	}
}

3.2. 交换

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

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

	if i >= 0 {
		//从右往左找到第一个比[i]大的数[k]
		k := len(nums) - 1
		for nums[i] >= nums[k] {
			k--
		}
		//交换[i], [k]
		nums[i], nums[k] = nums[k], nums[i]
	}

	//剩下的[j,end]是降序的，翻转一下
	reverse(nums, j, len(nums)-1)
}

func reverse(nums []int, left int, right int) {
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

4. 参考

• 下一个排列算法详解：思路+推导+步骤，看不懂算我输！ - 下一个排列 - 力扣（LeetCode）