#P4102. 下一个排序
-
ID: 2339
Tried: 74
Accepted: 19
Difficulty: 5
下一个排序
ACM 模式题目描述
题目描述
整数数组的一个 排列 是其所有元素的 线性顺序排列。
给定一个整数数组 nums，请计算其 下一个排列：
- 下一个排列是指 字典序更大的排列。
- 如果不存在下一个更大的排列，则将
nums重新排列为字典序最小的排列（即升序排列）。 - 必须原地修改，且只能使用 常数级额外空间。
输入描述
输入包含两行：
- 第一行输入一个整数 n（1≤n≤100），表示数组的长度。
- 第二行输入 n 个整数，表示数组
nums，其中 0≤nums[i]≤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
解题思路：下一个排列（字典序排列）
核心思想：
-
从后向前 找到第一对 升序对（即
nums[i] < nums[i+1]）。 -
找到比
nums[i]稍大的数nums[j]（从后往前查找）。 -
交换
nums[i]和nums[j]，使整体变大。 -
将
i之后的部分翻转，使其变成字典序最小的排列。
步骤
-
找到较小数
nums[i]：- 从后向前遍历
nums，找到 第一对升序 (nums[i] < nums[i+1]) 的索引i。 - 若 未找到（整个数组降序，如
[3,2,1]），直接 翻转整个数组，返回最小排列[1,2,3]。
- 从后向前遍历
-
找到较大数
nums[j]：- 从
nums[i+1:]里 找到比nums[i]大的最小元素nums[j]（从后向前找第一个nums[j] > nums[i]）。
- 从
-
交换
nums[i]和nums[j]：- 这样能使数组整体变大，同时保持
i之前的部分不变。
- 这样能使数组整体变大，同时保持
-
翻转
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;
}