原題
給定一個整型數(shù)組，找到所有主元素衩侥，它在數(shù)組中的出現(xiàn)次數(shù)嚴格大于數(shù)組元素個數(shù)的三分之一本砰。
給出數(shù)組**[1,2,1,2,1,3,3] **返回 1
解題思路
- 三三抵消，最后會剩下兩個candidates稠炬，但是注意此時不是誰占多數(shù)誰是最終結(jié)果，反例[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 4, 4] 三三抵消后剩下 [1, 4咪啡，4] 4數(shù)量占優(yōu)首启，但結(jié)果應(yīng)該是1，所以三三抵消后撤摸，再loop一遍找1和4誰數(shù)量超過了len(nums)/3
完整代碼
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
candidate1, count1 = None, 0
candidate2, count2 = None, 0
for num in nums:
if candidate1 == num:
count1 += 1
elif candidate2 == num:
count2 += 1
elif count1 == 0:
count1 += 1
candidate1 = num
elif count2 == 0:
count2 += 1
candidate2 = num
else:
count1 -= 1
count2 -= 1
count1, count2 = 0, 0
for num in nums:
if num == candidate1:
count1 += 1
if num == candidate2:
count2 += 1
result = []
if count1 > len(nums) / 3:
result.append(candidate1)
if count2 > len(nums) / 3:
result.append(candidate2)
return result
