首页 > 代码库 > Leetcode: Permutations II
Leetcode: Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.For example,[1,1,2] have the following unique permutations:[1,1,2], [1,2,1], and [2,1,1].
难度：80+15（怎样跳过重复的case来节省时间）。我一开始的想法很简单，就是在permutation这道题的基础上，在把合乎条件的permutation加入permutations的时候，加入一个查重语句。如果是重复的，就不添加。之前Subset II 问题我就是这么做的。
1 if (permutation.size() == num.length) {2 if (!permutations.contains(permutation)) {3 permutations.add(new ArrayList<Integer>(permutation));4 return;5 }6 }
可是这一次行不通了，报TLE。我就开始想，怎么节省时间呢？网上参看了别人的想法，说是对于重复的元素循环时跳过递归函数的调用。对题目这个例子来说就是，如果permutation已经计算过了[num[0], num[1], num[2]]即[1,1,2]这个case，那么之后如果permutation计算到[num[1], num[0], num[2]]又是[1,1,2]这个case的时候，需要跳过，不用算了。这样就可以剩下这部分递归的时间。
怎么知道当前的这个permutation之前出现过没有呢？（本题重点）
首先我们要对元素集合排序，从而让重复元素相邻，接下来就是一行代码对于重复元素和前面元素使用情况的判断。如果第一个重复元素前面的元素还没在当前结果中，那么我们不需要进行递归。
1 public class Solution { 2 public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { 3 Arrays.sort(num); 4 ArrayList<Integer> permutation = new ArrayList<Integer>(); 5 ArrayList<ArrayList<Integer>> permutations = new ArrayList<ArrayList<Integer>>(); 6 boolean[] visited = new boolean[num.length]; 7 helper(permutation, permutations, num, visited); 8 return permutations; 9 }10 11 public void helper(ArrayList<Integer> permutation, ArrayList<ArrayList<Integer>> permutations, int[] num, boolean[] visited) {12 if (permutation.size() == num.length) {13 permutations.add(new ArrayList<Integer>(permutation));14 return;15 }16 17 for (int k = 0; k < num.length; k++) {18 if (k > 0 && !visited[k-1] && num[k] == num[k-1]) continue; 19 if (!visited[k]) {20 visited[k] = true;21 permutation.add(num[k]);22 helper(permutation, permutations, num, visited);23 permutation.remove(permutation.size() - 1);24 visited[k] = false;25 }26 }27 }28 }
Leetcode: Permutations II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。