LeetCode-047-全排列|LeetCode-047-全排列 II
全排列 II
题目描述:给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。解法一:穷举法
示例说明请见LeetCode官网。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
【LeetCode-047-全排列|LeetCode-047-全排列 II】说明:其实本来想构造一棵多叉树,所有叶子节点到根节点的路径即为所有的路径排列,后来没用到,所以没有构造树的父子关系 。
- 首先,构造一棵多叉树MultiTree,该多叉树有以下几个属性,used表示当前路径已经走过的数组的位置,paths表示当前路径中的数字。
- 然后声明一个队列queue,队列的元素就是MultiTree,首先将nums中不同的数字出初始化成路径的第一个数字,然后加入到队列中(需要同时初始化used和paths)。
- 然后遍历队列queue,按照类似的方式将数组nums中没用到的数字加入到当前路径中(需要判断重复数字)。
- 直到队列中每一条路径的长度都和nums的长度一样,即已将所有的数字加入到路径中。
- 最后,返回队列中的所有的路径paths。
import java.util.*;
public class LeetCode_047 {/**
* 构造一棵多叉树
*/
static class MultiTree {
// 当前的值
public Integer val;
public MultiTree parent;
// 当前路径已经走过的数组的位置
public List used;
// 当前路径中的数字
public List paths;
public MultiTree(Integer val) {
this.val = val;
used = new ArrayList<>();
paths = new ArrayList<>();
}
}public static List> permuteUnique(int[] nums) {
Queue queue = new LinkedList<>();
Arrays.sort(nums);
int curNum = nums[0];
// 第一条路径
MultiTree first = new MultiTree(nums[0]);
first.paths.add(nums[0]);
first.used.add(0);
queue.add(first);
// 其他路径
for (int i = 1;
i < nums.length;
i++) {
if (nums[i] != curNum) {
MultiTree next = new MultiTree(nums[i]);
next.paths.add(nums[i]);
next.used.add(i);
queue.add(next);
curNum = nums[i];
}
}int length = 1;
while (length < nums.length) {
int count = queue.size();
while (count > 0) {
MultiTree curNode = queue.poll();
int firstNum = -1, firstNumIndex = -1;
// 找到第一个已有路径没经过的数
for (int i = 0;
i < nums.length;
i++) {
if (!curNode.used.contains(i)) {
firstNum = nums[i];
firstNumIndex = i;
MultiTree firstTree = new MultiTree(nums[i]);
firstTree.paths.addAll(curNode.paths);
firstTree.paths.add(firstNum);
firstTree.used.addAll(curNode.used);
firstTree.used.add(firstNumIndex);
queue.add(firstTree);
break;
}
}// 将其他不同的数也添加到新的路径
for (int i = firstNumIndex + 1;
i < nums.length;
i++) {
if (!curNode.used.contains(i) && nums[i] != firstNum) {
MultiTree otherTree = new MultiTree(nums[i]);
otherTree.paths.addAll(curNode.paths);
otherTree.paths.add(nums[i]);
otherTree.used.addAll(curNode.used);
otherTree.used.add(i);
queue.add(otherTree);
firstNum = nums[i];
}
}
count--;
}
length++;
}List> result = new ArrayList<>();
while (!queue.isEmpty()) {
result.add(queue.poll().paths);
}
return result;
}public static void main(String[] args) {
int[] nums = new int[]{1, 1, 2};
for (List integers : permuteUnique(nums)) {
for (Integer integer : integers) {
System.out.print(integer + " ");
}
System.out.println();
}
}
}
【每日寄语】 愿太阳的光辉始终洒在你心上。愿所有的不愉快,苦尽甘来。愿每个脆弱的人都能得到善待。愿现实有光,世界有暖。
推荐阅读
- 危险也是机会
- 活着就是生命的全部意义
- 一个健康的APP和健全的人格大体类似
- NeuVector 会是下一个爆款云原生安全神器吗()
- 全过程工程咨询——时间管理(12)
- 别墅庭院设计,不同的别墅庭院设计也给人视觉上完全不一样的!
- 不让记忆、感觉、情绪成为孩子的负累|不让记忆、感觉、情绪成为孩子的负累|《全脑教养法》(四)
- (全员向连载)云间当铺(一)
- 「按键精灵安卓版」关于全分辨率脚本的一些理解(非游戏app)
- 全职妈妈在4岁孩子眼中只是一个loser