Posted on 2023-10-06 20:31
Uriel 阅读(27)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code
给出一个数组，一共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