给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
数据范围： 
，数组中的值满足 
要求：空间复杂度 )
，时间复杂度
[编程题]有重复项数字的全排列
来个脑溢血解法，各位看官勿生气：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型一维数组
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
// 为了保证结果的字典升序，先对原始数组排序
Arrays.sort(num);
// 定义一个 list 用于记录结果数据
ArrayList<ArrayList<Integer>> encodeRes = new ArrayList<>();
ArrayList<ArrayList<Integer>> deCodeRes = new ArrayList<>();
// 再定义一个 双端队列来存储当前栈帧里面的数，主要用于回溯时增删
Deque<Integer> deque = new LinkedList<>();
HashMap<Integer, Integer> userHashMap = new HashMap<>();
// 定义一个标识，标识是否已经添加过当前元素
boolean[] usedArr = new boolean[num.length];
permuteHelper(encode(num, userHashMap), usedArr, encodeRes, deque);
// PriorityQueue
// 去重
HashMap<ArrayList<Integer>, Boolean> distinctMap = new HashMap<>();
for (ArrayList<Integer> inList : encodeRes) {
ArrayList<Integer> decode = decode(inList, userHashMap);
if (distinctMap.get(decode) == null) {
deCodeRes.add(decode);
distinctMap.put(decode, true);
}
}
return deCodeRes;
}
// 设计一种编码格式，对可能重复的数据进行不重复编码，最后还原
public static int[] encode(int[] num, Map<Integer, Integer> userHash) {
int[] resInt = new int[num.length];
for (int i = 0; i < num.length; i++) {
userHash.put(i + 1, num[i]);
resInt[i] = i + 1;
}
return resInt;
}
public static ArrayList<Integer> decode(ArrayList<Integer> num,
Map<Integer, Integer> userHash) {
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < num.size(); i++)
res.add(i, userHash.get(num.get(i)));
return res;
}
public static void permuteHelper(int[] num, boolean[] usedArr,
ArrayList<ArrayList<Integer>> res, Deque<Integer> usedDequeue) {
if (usedDequeue.size() == num.length) {
// 说明收集满了，开始装配
res.add(new ArrayList<>(usedDequeue));
return;
}
// 进行递归
for (int index = 0; index < num.length; index++) {
if (usedArr[index])
continue;
// 元素对应的位置，这样能保证输出时的顺序
usedArr[index] = true;
usedDequeue.add(num[index]);
permuteHelper(num, usedArr, res, usedDequeue);
// 弹栈后，尝试其它的递归，需要先复原状态, 仅保留 res 里面收集的元素
usedArr[index] = false;
usedDequeue.removeLast();
}
}
}
上一份
编辑于 2024-04-02 12:33:05
回复(0)
ArrayList<ArrayList<Integer>> res=new ArrayList<>();
public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
// write code here
Arrays.sort(num);
dfs(num ,new boolean[num.length] ,new ArrayList<>());
return res;
}
public void dfs(int[] num ,boolean[] flag ,ArrayList<Integer> list){
if(list.size()==num.length){
res.add(new ArrayList<Integer>(list));
return;
}
for(int i=0;i<num.length;i++){
// 跳过重复数据&nbs***bsp;已加入数据
if((i>0 && num[i]==num[i-1] && !flag[i-1]) || flag[i]){
continue;
}
flag[i]=true;
list.add(num[i]);
dfs(num ,flag ,list);
list.remove(list.size()-1);
flag[i]=false;
}
}
发表于 2024-03-09 14:38:07
回复(0)
数组有 重复元素，那么他们的索引肯定不重复，我这里通过比较 索引 和 索引的值，来确定排列的时候去除 重复的项；
当然，也可以用map来 存储 key: 索引，value: 值；但是 map后面还得转化成数组，还得迭代一下，所以我这里还是分开存储，值单独存在数组中，免得一次遍历；
import java.util.*;
public class Solution {
//声明几个全局的，懒得在迭代方法传值
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> arry = new ArrayList<>();
//既然元素有重复的，那么我们就拿索引出来排序，索引肯定不重复
ArrayList<Integer> index = new ArrayList<>();
// 入口方法
public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
//先按字典序排序
Arrays.sort(num);
permute(num);
return res;
}
//迭代方法
void permute(int[] num) {
//2.迭代终止条件
if (index.size() == num.length) {
res.add(new ArrayList<>(arry));
return;
}
//3.子部分执行方案
ArrayList<Integer> temp = new ArrayList<>(); //每一层，已经选过的数据
for (int i = 0; i < num.length; i++) {
//相同位置，或者值相同都不应该 选取
//（可以用map ， key存索引，值存数组的值，但是map最后输出成数组还得再迭代一下，所以这里索引和值还是分开处理吧）
if (index.contains(i) || temp.contains(num[i])) continue;
temp.add(num[i]);
index.add(i);
arry.add(num[i]);
//1.递归模型
permute(num);
//4. 回溯
index.remove(index.size() - 1);
arry.remove(arry.size() - 1);
}
}
}
发表于 2023-12-06 14:03:42
回复(0)
public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
//要先排序，从才能让相邻的元素挨着
Arrays.sort(num);
ArrayList<Integer> list=new ArrayList<>();
boolean[] used=new boolean[num.length];
build(num,ans,list,used);
return ans;
}
public void build(int[] num,ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> list,boolean[] used){
if(list.size()==num.length){
ans.add(new ArrayList<>(list));
}
for(int i=0;i<num.length;i++){
if(used[i]==true) continue;
if(i>0&&num[i]==num[i-1]&&used[i-1]==true) continue;
list.add(num[i]);
used[i]=true;
build(num,ans,list,used);
list.remove(list.size()-1);
used[i]=false;
}
}
发表于 2023-07-14 16:12:27
回复(1)
头大
import java.util.*;
import java.util.Collections;
import java.util.stream.Collectors;
public class Solution {
private ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> current = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
int max = getMax(num);
int[] countArr = new int[max + 1];
for (int idx = 0; idx < num.length; idx++) {
countArr[num[idx]]++;
}
dfsA(num, countArr, num.length);
Set<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>(all);
all.clear();
all.addAll(set);
Collections.sort(all, new Comparator<ArrayList<Integer>>() {
public int compare(ArrayList<Integer> self, ArrayList<Integer> other) {
int min = Math.min(self.size(), other.size());
for (int idx = 0; idx < min; idx++) {
if (self.get(idx) != other.get(idx)) {
return self.get(idx).compareTo(other.get(idx));
}
}
if (self.size() > other.size()) {
return self.get(min + 1);
} else if (self.size() < other.size()) {
return other.get(min + 1);
}
return 0;
}
});
return all;
}
public void dfsA(int[] num, int[] countArr, int n) {
if (current.size() == n) {
all.add((ArrayList<Integer>) current.clone());
return;
}
for (int i = 0; i < n; i++) {
int count = getCount(num[i]);
if (count < countArr[num[i]]) {
current.add(num[i]);
dfsA(num, countArr, n);
current.remove(current.size() - 1);
}
}
}
public int getCount(int num) {
long count = current.stream().filter(item -> item == num).collect(
Collectors.counting());
return Long.valueOf(count).intValue();
}
public static int getMax(int[] num) {
int max = Integer.MIN_VALUE;
for (int idx = 0; idx < num.length; idx++) {
if (max < num[idx]) {
max = num[idx];
}
}
return max;
}
}
发表于 2023-05-07 21:42:51
回复(0)
利用map记录每个数字出现的个数，遍历的时候只会遍历不同种类的数字，保证即使数字重复也只只会在一次选数中被选一次
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
TreeMap<Integer,Integer> treeMap = new TreeMap<>();
for(int i = 0; i<num.length;i++){
treeMap.put(num[i],treeMap.getOrDefault(num[i],0)+1);
}
tryMatch(treeMap,result,null);
return result;
}
public void tryMatch(TreeMap<Integer,Integer> map, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> preSequence) {
TreeMap<Integer,Integer> copy = new TreeMap<>(map);
for (Map.Entry<Integer,Integer> entry: map.entrySet()) {//遍历当前剩下的所有数字
Integer integer = entry.getKey();
ArrayList<Integer> p ;
if (preSequence == null) {
p = new ArrayList<Integer>();
} else {
p = new ArrayList<Integer>(preSequence);
}
p.add(integer);
if (map.size() > 1||entry.getValue()>1) {//数字种类大于1或者种类为1但数量大于1，需要继续递归
if(entry.getValue()<=1){//map中减少一个当前正在尝试的数字的数量（为0时直接移除这个key）
copy.remove(integer);
}else{
copy.put(integer,copy.get(integer)-1);
}
tryMatch(copy, result, p);//递归尝试
copy.put(integer,copy.getOrDefault(integer,0)+1);//恢复copy，以便操作下一个数字
} else {//不满足递归条件，视为当前尝试结束，尝试结果加入结果集
result.add(p);
}
}
}
}
发表于 2023-04-17 15:03:41
回复(0)
import java.util.*;
//正常排再去重
public class Solution {
ArrayList<ArrayList<Integer>> al = new ArrayList<>();
boolean[] dp;
public void back(int[] num, boolean[] dp, ArrayList<Integer> list) {
if (list.size() == num.length) {
al.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < num.length; i++) {
if (dp[i]) continue;
dp[i] = true;
list.add(num[i]);
back(num, dp, list);
list.remove(list.size() - 1);
dp[i] = false;
}
}
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
Arrays.sort(num);
dp = new boolean[num.length];
ArrayList<Integer> list = new ArrayList<>();
Arrays.fill(dp, false);
back(num, dp, list);
HashMap<ArrayList<Integer>, Integer> hs = new HashMap<>();
ArrayList<ArrayList<Integer>> al1 = new ArrayList<>();
for (int i = 0; i < al.size(); i++) {
ArrayList<Integer> a = al.get(i);
if (!hs.containsKey(a)) {
hs.put(a, 1);
al1.add(a);
}
}
return al1;
}
}
发表于 2023-03-23 13:43:18
回复(0)
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
Set<ArrayList<Integer>> res = new LinkedHashSet<>();
int length = 0; // 用于判断长度
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
Arrays.sort(num);
length = num.length;
// 使用列表方便做移除操作
List<Integer> nums = Arrays.stream(num).boxed().collect(Collectors.toList());
dfs(nums, new ArrayList<Integer>());
return new ArrayList<>(res);
}
private void dfs(List<Integer> num, ArrayList<Integer> integers) {
if (integers.size() == length) {
res.add(new ArrayList<>(integers));
}
for (int i = 0; i < num.size(); i++) {
// 不管，直接通过 set 来自动去重
integers.add(num.get(i));
// 每次生成一个新的列表来循环，这样下次循环次数减少，也不会重复
List<Integer> nextNum = new LinkedList<>(num);
nextNum.remove(i);
// 递归
dfs(nextNum, integers);
// 回溯
integers.remove(integers.size() - 1);
}
}
}
发表于 2023-03-17 10:32:18
回复(0)
递归方法用set集合存放用过的索引来排除重复引用；
最后再用set方法去重，与答案相比逊了一些但方便理解，同样通过。
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList();
Arrays.sort(num);
getResult(result, new ArrayList<Integer>(), num, new HashSet<>());
HashSet<String> hs = new HashSet<>();
result.removeIf(arrayList-> {
StringBuilder sb = new StringBuilder();
for (Integer integer : arrayList) {
sb.append(integer);
}
String concat = sb.toString();
boolean flag = false;
if (!hs.contains(concat)) {
hs.add(concat);
} else {
flag = true;
}
return flag;
});
return result;
}
private void getResult(ArrayList<ArrayList<Integer>> result,
ArrayList<Integer> ls, int[] num, HashSet<Integer> hs) {
if (ls.size() == num.length) {
result.add(new ArrayList<>(ls));
} else {
for (int i = 0; i < num.length; i++) {
if (hs.contains(i)) {
continue;
}
ls.add(num[i]);
hs.add(i);
getResult(result, ls, num, hs);
ls.remove(ls.size() - 1);
hs.remove(i);
}
}
}
}
发表于 2023-03-14 23:53:36
回复(0)
递归
import java.util.*;
public class Solution {
static ArrayList<ArrayList<Integer>> res = new ArrayList<>();
static boolean []mark;
public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
Arrays.sort(num);
mark = new boolean[num.length];
LinkedList<Integer> list = new LinkedList<>();
permute(num, list);
return res;
}
private static void permute(int[] num, LinkedList<Integer> list) {
// 递归的终结条件
if (num.length == list.size()) {
if (!res.contains(list)) {
res.add(new ArrayList<>(list));
}
return;
}
for (int i = 0; i < num.length; i++) {
if (mark[i]) {
continue;
}
list.add(num[i]);
mark[i] = true;
permute(num, list);
list.removeLast();
mark[i] = false;
}
}
}
发表于 2023-02-23 17:43:09
回复(0)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
Arrays.sort(num);
ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path=new ArrayList<Integer>();
dfs(num,path,list);
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();//去重后再装入list
for(int i=0;i<=list.size()-1;i++){//将list去重
if(res.contains(list.get(i))){continue;}
res.add(list.get(i));
}
return res;
}
public void dfs(int[] arr,ArrayList<Integer> path,ArrayList<ArrayList<Integer>> list){
if(path.size()==arr.length){
ArrayList<Integer> sublist=new ArrayList<Integer>();
for(int i=0;i<=path.size()-1;i++){
sublist.add(arr[path.get(i)]);
}
list.add(new ArrayList<Integer>(sublist));
return;
}
for(int i=0;i<=arr.length-1;i++){
if(path.contains(i)){continue;}
path.add(i);
dfs(arr,path,list);
path.remove(path.size()-1);
}
}
}
发表于 2022-08-03 16:36:10
回复(0)
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> track = new ArrayList<>();
boolean[] used;
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
used = new boolean[num.length];
Arrays.sort(num);
backtrack(num);
return res;
}
public void backtrack(int[] num){
if(track.size()==num.length) {
res.add(new ArrayList<Integer>(track));
return;
}
for(int i=0; i<num.length; i++){
if(used[i]) continue;
if(i>0 && num[i]==num[i-1] && !used[i-1]) continue;
used[i] = true;
track.add(num[i]);
backtrack(num);
track.remove(track.size()-1);
used[i] = false;
}
return;
}
}
发表于 2022-07-19 16:28:39
回复(0)
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<>(); //结果
LinkedList<Integer> path = new LinkedList<>(); //路径
boolean[] used;
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
if (num == null || num.length == 0) {
return res;
}
//数组排序，使相同元素挨着一起
Arrays.sort(num);
used = new boolean[num.length]; //标记每个元素是否使用过
backtracking(num);
return res;
}
void backtracking(int[] num) {
//结束条件
if (path.size() == num.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < num.length; i++) {
//元素已选择过
if (used[i] == true) {
continue;
}
//去重
if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) {
continue;
}
//做选择
used[i] = true;
path.add(num[i]);
backtracking(num);
//撤销选择
path.removeLast();
used[i] = false;
}
}
}
发表于 2022-07-03 16:04:57
回复(0)
private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
ArrayList<Integer> temp = new ArrayList<>();
Arrays.sort(num); //让数据有序
Boolean[] vis = new Boolean[num.length]; //加标志boolean
Arrays.fill(vis, false);
backtrack(num,temp,vis);
return res;
}
public void backtrack(int[] num,ArrayList<Integer> temp, Boolean[] vis){
if (temp.size() == num.length){
res.add(new ArrayList<Integer>(temp)); //需要new 因为temp不是局部变量 不安全
return;
}
//同层剪枝
for (int i = 0; i < num.length; i++){
if(vis[i]){
continue;
}
if(i > 0 && num[i - 1] == num[i] && !vis[i - 1])
//当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
continue;
//标记已经使用过
vis[i] = true;
//选择
temp.add(num[i]);
backtrack(num,temp,vis);
//撤销选择
temp.remove(temp.size()-1);
vis[i] = false;
}
}
发表于 2022-07-01 10:14:31
回复(0)
简单粗暴： DFS + 回溯
简单说明思路：【1，1，2】 只统计【1，2】
有数字重复时，采用对集合内容进行过滤，发现运行超时
private void dfs(int[] num, boolean[] flags, LinkedList<Integer> temp) {
// 结束标志
if (temp.size() == num.length && result.stream().noneMatch(o -> o.toString().equals(temp.toString()))) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < num.length; i++) {
if (flags[i]) {
continue;
}
// 前进
flags[i] = true;
temp.add(num[i]);
dfs(num, flags, temp);
// 回退
flags[i] = false;
temp.removeLast();
}
} 进行优化
import java.util.*;
public class Solution {
// 返回结果
private static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
Arrays.sort(num);
boolean[] flags = new boolean[num.length];
dfs(num, flags, new LinkedList<>());
return result;
}
private void dfs(int[] num, boolean[] flags, LinkedList<Integer> temp) {
// 结束标志
if (temp.size() == num.length) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < num.length; i++) {
if (flags[i] || i > 0 && num[i] == num[i - 1] && !flags[i - 1]) {
continue;
}
// 前进
flags[i] = true;
temp.add(num[i]);
dfs(num, flags, temp);
// 回退
flags[i] = false;
temp.removeLast();
}
}
}
发表于 2022-04-08 00:10:47
回复(0)
问题信息
难度：
43条回答
996收藏
29758浏览
通过挑战的用户
查看代码-
2022-11-15 14:45:08 -
2022-10-22 14:49:11
-
2022-10-13 22:13:58 -
2022-09-23 14:30:53
-
2022-09-20 16:37:23
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
