和上一道题类似，不同之处就是给定的数字中会有重复的，这样的话用之前的算法会产出重复的序列。例如，[ 1 1 ]，用之前的算法，产生的结果肯定是 [ [ 1 1 ]， [ 1 1 ] ]，也就是产生了重复的序列。但我们可以在上一题的解法中进行修改从而解决这道题。
解法一 插入
这个没想到怎么在原基础上改，可以直接了当些，在它产生的结果里，对结果去重再返回。对于去重的话，一般的方法肯定就是写两个 for 循环，然后一个一个互相比较，然后找到重复的去掉。这里，我们用 39题 解法二中提到的一种去重的方法。
publicList<List<Integer>>permuteUnique(int[] nums) { List<List<Integer>>all=newArrayList<>(); List<Integer>temp=newArrayList<>(); temp.add(nums[0]); all.add(temp); for (inti=1; i<nums.length; i++) { intcurrent_size=all.size(); for (intj=0; j<current_size; j++) { List<Integer>last=all.get(j); for (intk=0; k<=i; k++) { if (k<i&&nums[i] ==last.get(k)) { continue; } temp=newArrayList<>(last); temp.add(k, nums[i]); all.add(temp); } } for (intj=0; j<current_size; j++) { all.remove(0); } } returnremoveDuplicate(all); } privateList<List<Integer>>removeDuplicate(List<List<Integer>>list) { Map<String, String>ans=newHashMap<String, String>(); for (inti=0; i<list.size(); i++) { List<Integer>l=list.get(i); Stringkey=""; // [ 2 3 4 ] 转为 "2,3,4"for (intj=0; j<l.size() -1; j++) { key=key+l.get(j) +","; } key=key+l.get(l.size() -1); ans.put(key, ""); } // 根据逗号还原 ListList<List<Integer>>ans_list=newArrayList<List<Integer>>(); for (Stringk : ans.keySet()) { String[] l=k.split(","); List<Integer>temp=newArrayList<Integer>(); for (inti=0; i<l.length; i++) { intc=Integer.parseInt(l[i]); temp.add(c); } ans_list.add(temp); } returnans_list; }
解法二 交换
这个改起来相对容易些，之前的想法就是在每一个位置，让每个数字轮流交换过去一下。这里的话，我们其实只要把当前位置已经有哪些数字来过保存起来，如果有重复的话，我们不让他交换，直接换下一个数字就可以了。
publicList<List<Integer>>permuteUnique(int[] nums) { List<List<Integer>>all=newArrayList<>(); Arrays.sort(nums); upset(nums, 0, all); returnall; } privatevoidupset(int[] nums, intbegin, List<List<Integer>>all) { if (begin==nums.length) { ArrayList<Integer>temp=newArrayList<Integer>(); for (inti=0; i<nums.length; i++) { temp.add(nums[i]); } all.add(newArrayList<Integer>(temp)); return; } HashSet<Integer>set=newHashSet<>(); //保存当前要交换的位置已经有过哪些数字了for (inti=begin; i<nums.length; i++) { if (set.contains(nums[i])) { //如果存在了就跳过，不去交换continue; } set.add(nums[i]); swap(nums, i, begin); upset(nums, begin+1, all); swap(nums, i, begin); } } privatevoidswap(int[] nums, inti, intbegin) { inttemp=nums[i]; nums[i] =nums[begin]; nums[begin] =temp; }
总
基本上都是在上道题的基础上改出来了，一些技巧也是经常遇到，比如先排序，然后判断和前一个是否重复。利用 Hash 去重的功能。利用原来的存储空间隐藏掉数据，然后再想办法还原。
