Leetcode: Permutations II
LeetCode II Permutations
2023-09-11 14:14:08 时间
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: Circular Array Loop
- Leetcode: Design Hit Counter
- Leetcode: Add Two Numbers II
- Leetcode: Valid Perfect Square
- Leetcode: Search a 2D Matrix II
- Leetcode: Jump Game II
- Leetcode: Word Ladder II
- [LeetCode][Java] Container With Most Water
- 【Leetcode】101. 对称二叉树(简单)
- Leetcode 887.鸡蛋掉落(Hard)
- [LeetCode] Word Break II
- [LeetCode] Generate Parentheses
- 95、【树与二叉树】leetcode ——257. 二叉树的所有路径:递归法DFS/回溯法+迭代法DFS+层序遍历BFS(C++版本)
- 72、【哈希表】leetcode——454. 四数相加 II(C++版本)
- leetcode竞赛记录-第64场双周赛
- 【LeetCode】47. Permutations II
- [LeetCode] 1278. Palindrome Partitioning III 拆分回文串之三
- [LeetCode] 972. Equal Rational Numbers 相等的有理数
- [LeetCode] Stickers to Spell Word 贴片拼单词
- [LeetCode] Top K Frequent Words 前K个高频词
- [LeetCode] Valid Palindrome II 验证回文字符串之二
- [LeetCode] 454. 4Sum II 四数之和之二
- [LeetCode] 253. Meeting Rooms II 会议室之二
- [LeetCode] Move Zeroes 移动零
- [LeetCode] 126. Word Ladder II 词语阶梯之二
- [LeetCode] 40. Combination Sum II 组合之和之二
- [LeetCode] 47. Permutations II 全排列之二
- [LeetCode] Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树
- [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二
- LeetCode二叉树路径总和
- LeetCode 2. 两数相加
- leetcode 126. Word Ladder II 单词接龙 II(困难)