本文主要是介绍LeetCode--47. Permutations II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://leetcode.com/problems/permutations-ii/
这个题目就是跟https://blog.csdn.net/To_be_to_thought/article/details/85126156这篇思路类似，就是在46. Permutations的基础上用HashSet进行去重操作。代码的逻辑结构基本一致：
class Solution {public static List<List<Integer>> ret;public static boolean[] visited;public static int[] record;public static int num;public static HashSet<String> hs;public List<List<Integer>> permuteUnique(int[] nums) {ret=new LinkedList<List<Integer>>();num=nums.length;hs=new HashSet<String>();record=new int[num];visited=new boolean[num];recursive(nums,num);return ret;}public static void recursive(int[] nums,int k){if(k==0){StringBuilder sb=new StringBuilder();for(int i=0;i<num;i++)sb.append(record[i]);String st=sb.toString();if(hs.contains(st))return;else{hs.add(st);LinkedList<Integer> tmp=new LinkedList<Integer>();for(int i=0;i<num;i++)tmp.add(record[i]);ret.add(tmp);}}for(int i=0;i<nums.length;i++){if(!visited[i]){record[k-1]=nums[i];visited[i]=true;recursive(nums,k-1);visited[i]=false;}}}
}效率一如既往地很一般，是很菜！！！
我们能不能在搜索的时候就直接去重，避免生成序列后再检查。我们举个例子[3,3,0,3]看看为什么会产生重复。
原数组： 
如下两种选择产生的结果都一样，index是指选择的数在原数组中的索引：
当然，产生3330的结果不止这两种情况，我们发现在某个位置i上进行选数时，首先原数组中以前选过的位置上的数是不能选的，也就是需要一个访问记录数组来记录访问情况，另外在某个位置i上，遇到相等的数（之前在i位置上选过这个值，但不是这同一个位置）时，要判断上一次是否选择这个数，上次没选这个数值的这一次可以选，上次选了这个数值的不能选直接跳过。
除了在数组位置上不能重复选择（索引一致数值必然一致），在每个合法结果的位置i上选择也要判重（索引不一致，数值可能相同），这里采用HashSet做一下判重。代码如下：
class Solution {public static List<List<Integer>> ret;//存储最终答案public static boolean[] visited;//存储被选数组的索引访问记录public static int[] record;//存合法的每个答案public static int num;public List<List<Integer>> permuteUnique(int[] nums) {ret=new LinkedList<List<Integer>>();num=nums.length;record=new int[num];visited=new boolean[num];recursive(nums,num);return ret;}public static void recursive(int[] nums,int k){if(k==0){LinkedList<Integer> tmp=new LinkedList<Integer>();for(int i=0;i<num;i++)tmp.add(record[i]);ret.add(tmp);return;}HashSet<Integer> chosen=new HashSet<>(); for(int i=0;i<nums.length;i++){if(chosen.contains(nums[i]) || visited[i])continue;record[k-1]=nums[i];chosen.add(nums[i]);visited[i]=true;recursive(nums,k-1);visited[i]=false;}}
}还有一种比较奇怪的操作，效率更高，就是先将被选数组排序：
if(visited[i] || (i>0 && nums[i-1]==nums[i] && visited[i-1]))continue;和
if(visited[i] || (i>0 && nums[i-1]==nums[i] && !visited[i-1]))continue;都能AC
class Solution {public static List<List<Integer>> ret;public static boolean[] visited;public static int[] record;public static int num;public List<List<Integer>> permuteUnique(int[] nums) {ret=new LinkedList<List<Integer>>();num=nums.length;record=new int[num];visited=new boolean[num];Arrays.sort(nums);recursive(nums,num);return ret;}public static void recursive(int[] nums,int k){if(k==0){LinkedList<Integer> tmp=new LinkedList<Integer>();for(int i=0;i<num;i++)tmp.add(record[i]);ret.add(tmp);}for(int i=0;i<nums.length;i++){if(visited[i] || (i>0 && nums[i-1]==nums[i] && visited[i-1]))continue;record[k-1]=nums[i];visited[i]=true;recursive(nums,k-1);visited[i]=false;}}
}这篇关于LeetCode--47. Permutations II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
