【leetcode】169、Majority Element
2018-03-01 本文已影响0人
潇湘demi
翻译
找出多数，出现>n/2次的元素。
思路
Moore voting algorithm--每找出两个不同的element，就成对删除即count--，最终剩下的一定就是所求的（多数的元素>n/2）。时间复杂度：O(n)
a = ["a","c","b","c","a","a","a"]
def find_majory_number(a):
count =0
for iin range(len(a)):
if count==0:
majory = a[i]
count +=1
else:
if a[i] == majory:
count +=1
else:
count -=1
return majory
print find_majory_number(a)
