下一个排列

约 1190 字大约 4 分钟

2024-12-13

⭐️ 题目日期：

字节 - 2024/11/20，字节 - 2024/9/24

🌳 题目描述：

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

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

示例 1：
输入：nums = [1, 2, 3, 4, 5]
输出：[1, 2, 3, 5, 4]

解释图例：

🕵🏽 面试评估：

这道题考察候选人是否熟悉字典序排列的概念，是否能理解“从右向左遍历寻找升序对”和“局部最小调整”的核心思想，且能否熟练应用双指针方法来完成交换和反转操作。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

这道题的核心是理解下一个排列的生成规则。从数组 [1, 2, 3] 里不太容易发现规律。我们以更多元素的数组[1, 2, 3, 4, 5, 6] 为例：

[1, 3, 6, 5, 4, 2] 的下一个排列为[1, 4, 2, 3, 5, 6], 如何得来的？

从后向前寻找第一个元素，满足 nums[i] < nums[i + 1], 即第一个升序对 [3, 6]。为什么要找升序对？因为局部降序没法形成下一个排列。如[4, 2], [5, 4, 2], [6, 5, 4, 2] 皆为最大的排列，如果要找下一个排列，需要向前“进位”找一个更小的数来打破降序的僵局。
从遍历过的元素里，我们需要找出比 nums[i] 大的最小数，即从[6, 5, 4, 2] 里找比3大[6, 5, 4]的最小数为4。为什么要找最小数？如果选5，6就不是下一个排列了。
将找到的最小数 j 与 i 交换位置（将3与4交换位置），以新的 j 为首的排列必须从“零”开始，因为序列 [1, 4 X, X, X, X]从未出现，需要从最小的序列升序开始，即 [1, 4, 2, 3, 5, 6] 为下一个排列。如何排序？从降序[6, 5, 4, 2] 3与4交换后依然为降序 [6, 5, 3, 2], 用首尾双指针交换排序得 [2, 3, 5, 6]。

附上[1, 2, 3, 4, 5, 6] 前120个排列的列表帮助大家理解与验证规则：

💻代码：

Java

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int NON_EXIST_FLAG = -1;
        int targetIndex = NON_EXIST_FLAG;
        int n = nums.length;

        // 寻找第一个升序对
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                targetIndex = i;
                break;
            }
        }

        // 如果没有更大的排列，将数组重新升序排列
        if (targetIndex == NON_EXIST_FLAG) {
            sortSubarray(nums, 0, n - 1);
            return;
        }

        // 找到比 nums[targetIndex] 大的最小的数
        for (int i = n - 1; i > targetIndex; i--) {
            if (nums[i] > nums[targetIndex]) {
                swap(nums, i, targetIndex);
                break;
            }
        }
        
        // 将 targetIndex 右侧升序排列
        sortSubarray(nums, targetIndex + 1, n - 1);
    }

    private void sortSubarray(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

Python

    def nextPermutation(self, nums):
        if not nums or len(nums) <= 1:
            return
    
        n = len(nums)
        target_index = -1
    
        # 寻找第一个升序对
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                target_index = i
                break
    
        # 如果没有更大的排列，将数组重新升序排列
        if target_index == -1:
            nums.reverse()
            return
    
        # 找到比 nums[targetIndex] 大的最小的数
        for i in range(n - 1, target_index, -1):
            if nums[i] > nums[target_index]:
                # 交换两个数
                nums[i], nums[target_index] = nums[target_index], nums[i]
                break
    
        # 将 targetIndex 右侧升序排列
        left, right = target_index + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

🚵🏻复杂度分析：

时间复杂度：O(n)；数组中的每个元素最多访问 3 次，O(3n) = O(n)

空间复杂度：O(1)

🔬在线评测(Online Judge):

题目链接