Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一串可能重复的数,输出所有排列数,要求去重

思路一: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







只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理