算法题：优美的排列
对于每一个位置 i，数字 i 和数字 nums[i] 满足 i % nums[i] == 0或者nums[i] % i == 0。
n = 3，那我们要列出所有的排列 [1, 2, 3]，然后验证它们是否符合上述条件。如果是符合条件的排列，咱们就把它保留下来。import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> beautifulArrangements(int n) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> arrangement = new ArrayList<>();
boolean[] visited = new boolean[n + 1]; // 用来标记哪些数字已经被选过
backtrack(n, res, arrangement, visited);
return res;
}
private void backtrack(int n, List<List<Integer>> res, List<Integer> arrangement, boolean[] visited) {
if (arrangement.size() == n) {
res.add(new ArrayList<>(arrangement)); // 找到一个满足条件的排列
return;
}
for (int i = 1; i <= n; i++) {
if (visited[i]) continue; // 如果已经选择过该数字，跳过
if (arrangement.size() + 1 % i == 0 || i % (arrangement.size() + 1) == 0) { // 满足条件
arrangement.add(i);
visited[i] = true;
backtrack(n, res, arrangement, visited); // 递归选择下一个数字
visited[i] = false; // 回溯
arrangement.remove(arrangement.size() - 1);
}
}
}
}
backtrack 方法，我们试图生成一个所有符合条件的排列。每次递归时，我们都试图将一个数字 i 加入到当前排列中，并且检查它是否符合条件。如果符合条件，就继续递归，直到排列长度达到 n 为止。然后，我们把这个排列加入结果列表。如果当前数字不符合条件，就跳过它，回到上一步。visited 数组来确保每个数字只会出现在排列中一次。而且我们还在每次递归时验证 i % nums[i] == 0 或者 nums[i] % i == 0，这样保证了我们的排列符合题目要求。n 的值比较大时。因为在最坏的情况下，我们需要生成所有的排列，然后验证每个排列是否满足条件。生成所有排列的时间复杂度是 O(n!)，而每次验证排列的条件的时间复杂度是 O(n)。所以总体时间复杂度大约是 O(n * n!)，这对于较小的 n 是可以接受的，但如果 n 较大（比如超过 10），就会变得非常慢。-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
