Golang下一个排列算法解析

随笔记录， 下一个排列也就是说数据按字典中的顺序查找，举个例子提供了一个[9,8,6,9,4,6,5,3]序列，找他的下一个序列。

Leetcode举例如下： arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]

算法思路：

1、先确认组合是否为降序排列，如【3，2，1】，如果是完全降序，直接反转返回，即为下一个的结果。

2、如果不是完全降序，从倒数第一个开始查找一个下标（ 违反降序的下标 ）比如说[9,8,6,9, 4 ,6,5,3] 这组排列，数据4的下标就我们要的index=4。

3、接下来从【i,n-1】的范围中，从后向前查找查找一个比数据4大的交换数据。

4、反转【i+1】下标后的全部数据，即可得到下一个排列 [9,8,6,9,5,3,4,6] 。

代码如下：

下一个排序代码

 package main

import "fmt"

func main() {
data := []int{9, 8, 6, 9, 4, 6, 5, 3}
nextPermutation(data)
fmt.Println(data)
}

// 数组规律题
// 从后往前找第一个下降点 i，再从后往前找它的 ceil 值，交换
// 再将 [i+1:] 之后的数据从降序反转为升序，为最小序列
func nextPermutation(nums []int) {
// 处理降序的 case
desc := true
n := len(nums)

// 最小反转
for i := range nums[:n-1] {
if nums[i] < nums[i+1] {
desc = false
}
}
if desc {
reverse(nums)
return
}

// 从后向前找第一个下降的点
var i int
for i = n - 1; i > 0; i-- {
if nums[i-1] < nums[i] {
i-- // 找到 2
break
}
}

// 从后向前，找向上最接近的值
for j := n - 1; j > i; j-- {
if nums[j] > nums[i] {
nums[j], nums[i] = nums[i], nums[j] // 交换 2 和 3     // [1 3 7 4 2 1]
break
}
}

reverse(nums[i+1:]) // 反转 4 2 1    // [1 3 1 2 4 7]
}

func reverse(a []int) {
for i, n := 0, len(a); i < n/2; i++ {
a[i], a[n-1-i] = a[n-1-i], a[i]
}
}