首页 > 代码库 > 47. Permutations II
47. Permutations II
一、题目
1、描述
2、题意
给出一个可以重复数值的整形数组，求所有不同的排序！
二、解答
1、思路：
采用全排序，全排序中再去除重复的组合。其中，全排序采用深度优先排序，即一层层往下递归，走到底，再往上一个一个回溯。其中，很巧妙的的在 调用DFS前交换一个元素，DFS方法后在交换回来，保持能够递归出所有的排序！
错误：
①去重可以将数组元素排序，后依次遍历，当后面一个元素与前一个相等时，直接i++，因为前面的元素开始递归时已经包含了所有后面一个元素开始递归的情况。
②去重 利用 if(i != index && nums[i] == nums[i-1]) continue; 错误
正确： 利用 Set 去重，add 方法，当存在该元素时，Set 为改变返回 false。
public List<List<Integer>> permuteUnique(int[] nums) { // 全排列 Arrays.sort(nums); List<List<Integer>> resultList = new ArrayList<List<Integer>>(); // DFS permuteDFS(resultList, nums, 0); return resultList; } private void permuteDFS(List<List<Integer>> resultList, int[] nums, int index) { if(index >= nums.length) { ArrayList<Integer> targetList = new ArrayList<Integer>(); for(int i : nums) targetList.add(i); resultList.add(targetList); return; } Set<Integer> appeared = new HashSet<>(); for (int i = index; i < nums.length; i++) { if(appeared.add(nums[i])) { swap(nums, i, index); permuteDFS(resultList, nums, index+1); swap(nums, i, index); } //while(i < nums.length-1 && nums[i+1] == nums[i]) i++; } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
三、总结：
还未真正掌握
47. Permutations II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。