下一个排列 | 梧席

题目描述

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案

import "sort"
func nextPermutation(nums []int)  {
    // 记录nums长度len
    lenn := len(nums)
    if(lenn == 1){
        return
    }
    // 从下标 len-1 开始到下标 1 结束，
    // 匹配第一个 nums[i] > nums[i-1],mindex := i-1
    mindex := 0
    for mindex = lenn-1;mindex > 0 && nums[mindex] <= nums[mindex-1];mindex--{}
	// 如果 mindex == 0 则说明 nums 已经为降序，直接返回它转换为升序
    if mindex == 0{
        sort.Sort(sort.IntSlice(nums))
        return
    }
    mindex = mindex-1
    // 再由 num[mindex+1] 到 num[lenn-1]进行回溯，
    // 找到第一个 num[q] <= num[mindex],
    q := mindex
    for q = mindex+1;q < lenn && nums[q] > nums[mindex];q++{}
    // 则 num[q-1] 就是我们所要找的，
    q = q - 1
    // 交换 num[q-1] 和 num[mindex] 的值，
    nums[mindex],nums[q] = nums[q],nums[mindex]

    // 最后对下标 mindex+1 到 len-1 进行升序排序
    if q < lenn{
        sort.Sort(sort.IntSlice(nums[mindex+1:]))
    }
    return
}

挺简单一题，分析好线性排列的逻辑关系就行了

解题思路

1　　2　　7　　4　　3　　1

下一个排列为：

1　　3　　1　　2　　4　　7

那么是如何得到的呢，步骤如下：

从后往前，找到最长的降序排列

1　　2　　7　　4　　3　　1

把这个降序排列，转换成升序排列

1　　2　　1　　3　　4　　7

把序列前的元素，与序列中，第一个大于他的元素互换。

1　　3　　1　　2　　4　　7

题解

func nextPermutation(a []int) {
	left := len(a) - 2
	for 0 <= left && a[left] >= a[left+1] {
		left--
	}

	// 此时 a[left+1:] 是一个 递减 数列

	reverse(a, left+1)

	if left == -1 {
		return
	}

	// 此时 a[left+1:] 是一个 递增 数列

	right := search(a, left+1, a[left])
	a[left], a[right] = a[right], a[left]
}

// 逆转 a[l:]
func reverse(a []int, l int) {
	r := len(a) - 1
	for l < r {
		a[l], a[r] = a[r], a[l]
		l++
		r--
	}
}

// 返回 a[l:] 中 > target 的最小值的索引号
// a[l:] 是一个 递增 数列
func search(a []int, l, target int) int {
	r := len(a) - 1
	l--
	for l+1 < r {
		mid := (l + r) / 2
		if target < a[mid] {
			r = mid
		} else {
			l = mid
		}
	}
	return r
}

总结

分析