全排列 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
代码结果
运行时间: 52 ms, 内存: 15.3 MB
/*
* 思路：
* 1. 利用Java Stream API来生成排列。
* 2. 使用Map来统计每个数字的出现次数，避免重复排列。
* 3. 使用递归和流的扁平映射操作来生成排列。
*/
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Map<Integer, Long> counter = Arrays.stream(nums).boxed()
.collect(Collectors.groupingBy(n -> n, Collectors.counting()));
return permute(new LinkedList<>(), nums.length, counter).collect(Collectors.toList());
}
private Stream<List<Integer>> permute(LinkedList<Integer> current, int n, Map<Integer, Long> counter) {
if (current.size() == n) {
return Stream.of(new ArrayList<>(current));
}
return counter.entrySet().stream()
.filter(entry -> entry.getValue() > 0)
.flatMap(entry -> {
current.add(entry.getKey());
counter.put(entry.getKey(), entry.getValue() - 1);
Stream<List<Integer>> result = permute(current, n, counter);
current.removeLast();
counter.put(entry.getKey(), entry.getValue());
return result;
});
}
}
解释
方法:
这个题解使用了回溯算法。首先对数组进行排序，然后使用递归的方式生成所有排列。为了避免生成重复的排列，在每一层递归中，如果当前元素和前一个元素相同，则跳过该元素。另外，为了避免在递归过程中重复使用同一个元素，使用 None 标记已经使用过的元素。
时间复杂度:
O(n * n!)
空间复杂度:
O(n * n!)
代码细节讲解
🦆
为什么在回溯算法中首先需要对数组进行排序？排序对于避免重复排列有什么帮助？
▷🦆
在回溯过程中，使用`None`来标记已经使用过的元素是否是最优的方法？是否有其他方式可以追踪元素的使用状态？
▷🦆
题解中提到如遇到当前元素与前一个元素相同就跳过，这种方法是否确保了所有不重复的全排列都被正确生成，还是可能漏掉某些排列？
▷🦆
在实现中，为什么在每次递归调用`backtrack`之后需要执行`nums[i] = path.pop()`这一步？这样做有什么特别的目的或好处？
▷相关问题
下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
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