解题思路：下一个排列（字典序排列）

核心思想：

• 从后向前 找到第一对 升序对（即 nums[i] < nums[i+1]）。

• 找到比 nums[i] 稍大的数 nums[j]（从后往前查找）。

• 交换 nums[i] 和 nums[j]，使整体变大。

• 将 i 之后的部分翻转，使其变成字典序最小的排列。

步骤

1. 找到较小数 nums[i]：

   • 从后向前遍历 nums，找到 第一对升序 (nums[i] < nums[i+1]) 的索引 i。
   • 若 未找到（整个数组降序，如 [3,2,1]），直接 翻转整个数组，返回最小排列 [1,2,3]。

2. 找到较大数 nums[j]：

   • 从 nums[i+1:] 里 找到比 nums[i] 大的最小元素 nums[j]（从后向前找第一个 nums[j] > nums[i]）。

3. 交换 nums[i] 和 nums[j]：

   • 这样能使数组整体变大，同时保持 i 之前的部分不变。

4. 翻转 nums[i+1:]：

   • 使 i 之后的部分变成 最小字典序排列。

时间 & 空间复杂度

• 时间复杂度：$O(n)$，最多遍历 3 次数组（找到 i、找到 j、翻转）。
• 空间复杂度：$O(1)$，原地修改，不占用额外空间。

Python 代码

import sys

def next_permutation(nums):
    """ 计算数组的下一个排列 """
    n = len(nums)
    
    # 1. 找到第一个下降的位置 i
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:  # 存在下一个排列
        # 2. 找到比 nums[i] 大的最小元素 nums[j]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        # 交换 nums[i] 和 nums[j]
        nums[i], nums[j] = nums[j], nums[i]

    # 3. 反转 i+1 之后的部分，使其最小化
    nums[i + 1:] = reversed(nums[i + 1:])

def main():
    """ 读取输入并调用求解函数 """
    n = int(sys.stdin.readline().strip())  # 读取数组长度
    nums = list(map(int, sys.stdin.readline().strip().split()))  # 读取数组
    next_permutation(nums)  # 计算下一个排列
    print(" ".join(map(str, nums)))  # 输出结果

if __name__ == "__main__":
    main()

Java 代码

import java.util.*;

public class Main {
    public static void nextPermutation(int[] nums) {
        int n = nums.length, i = n - 2;

        // 1. 找到第一个下降的位置 i
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) { // 存在下一个排列
            // 2. 找到比 nums[i] 大的最小元素 nums[j]
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            // 交换 nums[i] 和 nums[j]
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        // 3. 反转 i+1 之后的部分
        reverse(nums, i + 1, n - 1);
    }

    private static void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 读取数组长度
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        nextPermutation(nums);  // 计算下一个排列
        for (int i = 0; i < n; i++) {
            System.out.print(nums[i] + (i == n - 1 ? "\n" : " "));
        }
        sc.close();
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void nextPermutation(vector<int>& nums) {
    int n = nums.size(), i = n - 2;

    // 1. 找到第一个下降的位置 i
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    if (i >= 0) { // 存在下一个排列
        // 2. 找到比 nums[i] 大的最小元素 nums[j]
        int j = n - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        // 交换 nums[i] 和 nums[j]
        swap(nums[i], nums[j]);
    }

    // 3. 反转 i+1 之后的部分
    reverse(nums.begin() + i + 1, nums.end());
}

int main() {
    int n;
    cin >> n;  // 读取数组长度
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    nextPermutation(nums);  // 计算下一个排列
    for (int i = 0; i < n; i++) {
        cout << nums[i] << (i == n - 1 ? "\n" : " ");
    }
    return 0;
}

Leetcode 99.下一个排序-原题链接

ACM 模式题目描述

题目描述

整数数组的一个 排列 是其所有元素的 线性顺序排列。

给定一个整数数组 nums，请计算其 下一个排列：

• 下一个排列是指 字典序更大的排列。
• 如果不存在下一个更大的排列，则将 nums 重新排列为字典序最小的排列（即升序排列）。
• 必须原地修改，且只能使用 常数级额外空间。

输入描述

输入包含两行：

• 第一行输入一个整数 $n$（$1 \leq n \leq 100$），表示数组的长度。
• 第二行输入 $n$ 个整数，表示数组 nums，其中 $0 \leq nums[i] \leq 100$。

输出描述

输出一行，表示数组 nums 的 下一个排列，元素之间用 空格 分隔。

样例输入 1

3
1 2 3

样例输出 1

1 3 2

样例输入 2

3
3 2 1

样例输出 2

1 2 3

样例输入 3

3
1 1 5

样例输出 3

1 5 1