Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个数组,一共n个数,输出其中出现次数大于n/3(下取整)的数
可以用python的Counter,或者Boyer-Moore Majority Voting

 1 #229
 2 #Runtime: 82 ms (Beats 66.93%)
 3 #Memory: 14.3 MB (Beats 72.83%)
 4 
 5 class Solution(object):
 6     def majorityElement(self, nums):
 7         """
 8         :type nums: List[int]
 9         :rtype: List[int]
10         """
11         cnt1 = cnt2 = 0
12         candidate1 = candidate2 = 0
13         for n in nums:
14             if cnt1 == 0 and candidate2 != n:
15                 cnt1 = 1
16                 candidate1 = n
17             elif cnt2 == 0 and candidate1 != n:
18                 cnt2 = 1
19                 candidate2 = n
20             elif candidate1 == n:
21                 cnt1 += 1
22             elif candidate2 == n:
23                 cnt2 += 1
24             else:
25                 cnt1 -= 1
26                 cnt2 -= 1
27         ans = []
28         thr = len(nums) // 3
29         cnt1 = cnt2 = 0
30         for n in nums:
31             if candidate1 == n:
32                 cnt1 += 1
33             elif candidate2 == n:
34                 cnt2 += 1
35         if cnt1 > thr:
36             ans.append(candidate1)
37         if cnt2 > thr:
38             ans.append(candidate2)
39         return ans

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