全排列
难度:
标签:
题目描述
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
代码结果
运行时间: 32 ms, 内存: 15.1 MB
/*
题目思路：
1. 使用Java Stream API来实现全排列生成。
2. 利用Stream的flatMap和collect方法，通过递归的方式构建所有可能的排列。
3. 在递归过程中，每次选择一个数字作为当前排列的下一个元素，并将其从剩余的数字中移除。
*/
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class PermutationsStream {
public List<List<Integer>> permute(int[] nums) {
return permute(Arrays.stream(nums).boxed().collect(Collectors.toList())).collect(Collectors.toList());
}
private Stream<List<Integer>> permute(List<Integer> nums) {
if (nums.size() == 1) {
return Stream.of(nums);
}
return nums.stream().flatMap(n -> permute(nums.stream()
.filter(x -> x != n)
.collect(Collectors.toList()))
.map(t -> Stream.concat(Stream.of(n), t.stream())
.collect(Collectors.toList())));
}
}
解释
方法:
这个题解使用了回溯算法。首先定义了一个 backtrack 函数，它接收一个 path 参数表示当前的排列路径。如果 path 的长度等于 nums 的长度，说明找到了一个完整的排列，将其加入结果列表中并返回。否则，遍历 nums 中的每个元素，如果该元素还没有被使用过（即不为 None），就将其加入到 path 中，并将该元素在 nums 中标记为 None 表示已使用。然后递归调用 backtrack 函数，继续搜索下一个位置的元素。当递归返回时，将之前标记为 None 的元素恢复为原来的值，并从 path 中移除，以便尝试其他的排列方式。最后，在主函数中调用 backtrack 函数，并传入一个空的 path，开始搜索所有可能的排列。
时间复杂度:
O(n * n!)
空间复杂度:
O(n * n!)
代码细节讲解
🦆
为什么在回溯算法中，需要将已选元素标记为 None，而不是直接从 nums 数组中删除它？
▷🦆
在回溯过程中，每次递归调用 backtrack 之后，为什么要恢复 nums[i] 的原始值并从 path 中移除最后一个元素？
▷🦆
如果 nums 数组中包含重复元素，现有的算法还能正确工作吗？如果不能，需要做哪些调整？
▷🦆
在回溯算法中，使用 list(path) 而非直接使用 path 添加到结果集中的原因是什么？
▷相关问题
下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 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 <= nums.length <= 1000 <= nums[i] <= 100
全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10