31.下一个排列

Bin大约 4 分钟

题目描述

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外 O(1) 的空间。

示例 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, 2, 3]，它的所有排列按字典序是： [1, 2, 3] -> [1, 3, 2] -> [2, 1, 3] -> [2, 3, 1] -> [3, 1, 2] -> [3, 2, 1]

下一个排列就是要找到比当前排列“大一点点”的那个。我们希望这个“大”的增幅尽可能小，所以我们需要在尽可能靠右的位置进行修改。

让我们以 [1, 5, 8, 4, 7, 6, 5, 3, 1] 为例来寻找下一个排列 [1, 5, 8, 5, 1, 3, 4, 6, 7]。

算法步骤

从后向前查找第一个“小数” 我们从数组的末尾开始向前遍历，找到第一个满足 nums[i] < nums[i + 1] 的索引 i。这个 nums[i] 就是我们要操作的“小数”。
- 对于 [1, 5, 8, 4, 7, 6, 5, 3, 1]，从后往前看，3>1, 5>3, 6>5, 7>6，直到 4 < 7。所以，我们找到了 i = 3，对应的 nums[i] 是 4。
- 为什么这么找？因为 i 右边的部分 [7, 6, 5, 3, 1] 是一个降序排列，它已经是这几个数字能组成的最大排列了。要找到下一个更大的排列，必须用 i 右边的一个比 nums[i] 大的数来替换它。
从后向前查找第一个“大数” 再次从数组的末尾开始向前遍历，找到第一个满足 nums[j] > nums[i] 的索引 j。这个 nums[j] 就是我们要用来和 nums[i] 交换的“大数”。
- 对于 [1, 5, 8, 4, 7, 6, 5, 3, 1] 和 i = 3 (nums[i]=4)，从后往前找，1<4, 3<4，直到 5 > 4。所以，我们找到了 j = 6，对应的 nums[j] 是 5。
- 为什么这么找？因为我们要让排列的增幅尽可能小，所以要用 i 右边比 nums[i] 大的数中最小的那个来交换。由于 i 右边的序列是降序的，所以从后往前找到的第一个大于 nums[i] 的数就是我们要的“大数”。
交换“小数”和“大数” 交换 nums[i] 和 nums[j]。
- 交换 nums[3] 和 nums[6]，数组变为 [1, 5, 8, 5, 7, 6, 4, 3, 1]。
反转 i 后面的序列 此时，i 位置的数字已经变大了，为了让整个排列是“下一个”更大的排列（即增幅最小），我们需要让 i 后面的部分变为最小的排列，也就是升序排列。
- 由于在步骤 1 和 2 之后，i 后面的序列 [7, 6, 4, 3, 1] 仍然是降序的，我们只需要将它直接反转，就能得到升序排列 [1, 3, 4, 6, 7]。
- 反转后，数组最终变为 [1, 5, 8, 5, 1, 3, 4, 6, 7]，这就是我们想要的答案。

特殊情况： 如果在步骤 1 中没有找到 nums[i] < nums[i + 1]，说明整个数组是降序的（如 [3, 2, 1]），它已经是最大的排列了。此时，直接将整个数组反转，得到最小的排列 [1, 2, 3]。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        solution.nextPermutation(nums);

        // 输出下一个排列
        for (int i = 0; i < n; i++) {
            System.out.print(nums[i]);
            if (i < n - 1) System.out.print(" ");
        }
        System.out.println();

        scanner.close();
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        // 1. 从后往前找，找到第一个"小数" i
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // 如果找到了 i，说明不是完全降序
        if (i >= 0) {
            // 2. 从后往前找，找到第一个比 nums[i] 大的"大数" j
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            // 3. 交换
            swap(nums, i, j);
        }

        // 4. 反转 i 后面的部分（如果 i = -1，则反转整个数组）
        reverse(nums, i + 1);
    }

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

    private void reverse(int[] nums, int start) {
        int left = start;
        int right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

复杂度分析

时间复杂度：O(n)
- 整个过程最多对数组进行两次遍历，一次是找 i 和 j，一次是反转。
空间复杂度：O(1)
- 只使用了常数个额外变量，满足原地修改的要求。
保持后半段的递减，那么只能前面动手脚，找到小的，然后换位，再把递增反转就是当前最小