下一个排列

Source: Dev.to

问题描述

任务是计算给定数字数组的 下一个排列。
排列是相同元素的重新排列，而 下一个排列 是字典序上比当前排列大的最小排列。

算法

1. 从末尾找到第一个下降的元素

从右向左遍历数组，定位第一个满足 nums[i] > nums[i+1] 的索引 i（即 nums[i] 大于其右侧元素）。

2. 在后缀中找到比 nums[i] 稍大的元素

在索引 i 右侧的子数组中，找到第一个大于 nums[i] 的元素 nums[j]（从右端开始搜索）。

3. 交换并翻转后缀

交换 nums[i] 与 nums[j]。随后将子数组 nums[i + 1:] 反转，以得到可能的最小后缀，完成下一个排列。

实现 (Python)

def nextPermutation(nums):
    n = len(nums)
    i = n - 2
    # Step 1: find the first decreasing element
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # Step 2: find the element just larger than nums[i]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        # Step 3: swap
        nums[i], nums[j] = nums[j], nums[i]

    # Step 4: reverse the suffix
    nums[i + 1:] = reversed(nums[i + 1:])

示例

nums = [2, 1, 5, 4, 3, 0, 0]
print("Original:", nums)

nextPermutation(nums)
print("Next Permutation:", nums)

输出

Original: [2, 1, 5, 4, 3, 0, 0]
Next Permutation: [2, 3, 0, 0, 1, 4, 5]