Posted on 2022-11-06 19:32
Uriel 阅读(42)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
闲来无事重切Leet Code
给出一串可能重复的数，输出所有排列数，要求去重思路一：Python的生成排列的函数，再去重（需要先排序，方便后续去重，非常耗时且需要更多Memory）：
Runtime: 575 ms, faster than 31.05% of Python online submissions for Permutations II.
Memory Usage: 20.6 MB, less than 5.10% of Python online submissions for Permutations II.
1 #47
2 #Runtime: 575 ms
3 #Memory Usage: 20.6 MB
4
5 class Solution(object):
6 def permuteUnique(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[List[int]]
10 """
11 nums.sort()
12 t_ans = list(permutations(nums))
13 ans = []
14 ans.append(t_ans[0])
15 for i in range(1, len(t_ans)):
16 fg = 0
17 nt = 0
18 for j in range(0, len(t_ans[i])):
19 if t_ans[i][j] == ans[-1][j]:
20 nt += 1
21 if j > 0 and t_ans[i][j - 1] == ans[-1][j - 1] and t_ans[i][j] < ans[-1][j]:
22 fg = 1
23 break
24 if fg == 0 and nt < len(nums):
25 ans.append(t_ans[i])
26 return ans
思路二：用Python的Counter函数记录每一种数字出现的次数，在DFS时只记录是否每个数字用完了，而不是每一位是否visit，以达到去重作用
1 #47
2 #Runtime: 77 ms
3 #Memory Usage: 13.8 MB
4
5 class Solution(object):
6
7 def permuteUnique(self, nums):
8 """
9 :type nums: List[int]
10 :rtype: List[List[int]]
11 """
12 vis = Counter(nums)
13 self.res = []
14 self.dfs(nums, vis, [])
15 return self.res
16
17 def dfs(self, nums, vis, s):
18 if len(s) == len(nums):
19 self.res.append(list(s))
20 return
21 else:
22 for i in vis:
23 if vis[i] > 0:
24 vis[i] -= 1
25 s.append(i)
26 self.dfs(nums, vis, s)
27 s.pop()
28 vis[i] += 1