31. 下一个排列(Medium)

题目描述

实现获取 下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

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

样例

Input: nums = [1,2,3]
Output: [1,3,2]

Input: nums = [3,2,1]
Output: [1,2,3]

Go 示例

func reverse(nums *[]int, l int, r int) {
    for l < r {
        (*nums)[l], (*nums)[r] = (*nums)[r], (*nums)[l]
        l++
        r--
    }
}

func nextPermutation(nums []int)  {
    // 两遍循环
    // 第一遍循环: 从右向左，找到第一个顺序对，如 1 2 4 3 中 (2, 4) (i = 2)
    // 第二遍循环: 从右向左，找到第一个大于 i 的数字，即 j = 3
    // 交换 i, j: 1 2 4 3 -> 1 3 4 2 
    // i 之后的位置倒序排列 1 3 | 4 2 -> 1 3 | 2 4

    var i, j int 
    for i = len(nums) - 2; i >= 0 && nums[i] >= nums[i + 1]; { // 寻找 nums[i] < nums[i + 1], 所以一定是 >= ！！！！！ 
        i--
    } 
        
    if i >= 0 { // i 可能为 -1 如 4 3 2 1
        for j = len(nums) - 1; j >= 0 && nums[j] <= nums[i]; { 
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    reverse(&nums, i + 1, len(nums) - 1)  // 原地翻转，使用指针
}

Python 示例

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(n - 2, -2, -1): # 注意，这里要让 -1 可以取到
            if nums[i] < nums[i + 1]:
                break 
        if i >= 0: # 判断 -1 
            for j in range(n - 1, i, -1):
                if nums[j] > nums[i]: # 
                    break
            nums[i], nums[j] = nums[j], nums[i]
        # i + 1 之后进行翻转
        start, end = i + 1, n - 1
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1