排列
题目 排列
思路分析
java中没有next_permutation 得老老实实写dfs 最后附上next_permutation实现
代码实现
import java.util.Scanner;
import java.io.*;
public class Main {
// 存储当前排列路径的数组
private static int[] path;
// 标记数组，用于标记某个元素是否已在当前排列中使用
private static boolean[] st;
// 输入的整数 n，表示要排列的数字的范围是 [1, n]
private static int n;
// 使用 BufferedWriter 来高效地输出结果
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
path = new int[n];
st = new boolean[n];
dfs(0);
bw.flush();// 刷新缓冲区，将所有内容输出
}
private static void dfs(int u) throws Exception {
if (u == n) {
for (int i = 0; i < n; i++)
bw.write(path[i] + " ");
bw.write("\n");
} else {
for (int i = 0; i < n; i++)
if (!st[i]) {
st[i] = true;
path[u] = i + 1;
dfs(u + 1);
st[i] = false;
}
}
}
}
不使用静态变量也能让dfs函数访问到局部变量的方法：
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
boolean[] vis = new boolean[n];
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 局部内部类可以访问外部类的所有成员变量和方法
class Inner {
public void dfs(int u) throws IOException {
if (u == n) {
for (int i = 0; i < n; i++) {
bw.write((nums[i] + 1) + " ");
}
bw.write("\n");
} else {
for (int i = 0; i < n; i++) {
if (vis[i] == false) {
vis[i] = true;
nums[u] = i;
dfs(u + 1);
vis[i] = false;
}
}
}
}
}
Inner inner = new Inner();
inner.dfs(0);
bw.flush();
}
}
next_permutation实现
- 从右往左找到第一个递增的位置
i（即找到第一个满足a[i] < a[i + 1]的i）。 - 从右往左找到第一个比
a[i]大的数字j。 - 交换
a[i]和a[j]。 - 反转
i + 1之后的子数组。
基本实现 tle：
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
// 初始化数组 a 为 [1, 2, 3, ..., n]
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}
// 打印初始排列
do {
for (int num : a) {
System.out.print(num + " ");
}
System.out.println();
} while (nextPermutation(a)); // 生成下一个排列，直到没有更大的排列
}
// 实现类似 C++ 中 next_permutation 的方法
private static boolean nextPermutation(int[] a) {
int i = a.length - 2;
// 从右往左找到第一个递增的位置 i
while (i >= 0 && a[i] >= a[i + 1]) {
i--;
}
// 如果 i < 0，说明当前排列是最大的，返回 false 表示没有下一个排列了
if (i < 0) return false;
int j = a.length - 1;
// 从右往左找到第一个比 a[i] 大的元素 j
while (a[j] <= a[i]) {
j--;
}
// 交换 a[i] 和 a[j]
swap(a, i, j);
// 反转 i + 1 之后的元素
reverse(a, i + 1, a.length - 1);
return true;
}
// 辅助方法：交换数组中的两个元素
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// 辅助方法：反转数组中从 start 到 end 的部分
private static void reverse(int[] a, int start, int end) {
while (start < end) {
swap(a, start, end);
start++;
end--;
}
}
}
结合BufferedWriter 优化 I/O ac
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
do {
for (int num : a) {
bw.write(num + " ");
}
bw.write("\n");
} while (nextPermutation(a));
bw.flush();
bw.close();
}
private static boolean nextPermutation(int[] a) {
int i = a.length - 2;
while (i >= 0 && a[i] >= a[i + 1]) {
i--;
}
if (i < 0) return false;
int j = a.length - 1;
while (a[j] <= a[i]) {
j--;
}
swap(a, i, j);
reverse(a, i + 1, a.length - 1);
return true;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static void reverse(int[] a, int start, int end) {
while (start < end) {
swap(a, start, end);
start++;
end--;
}
}
}
💬 评论