【題目描述】數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字购撼。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}蔬将。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半渡八，因此輸出2啃洋。如果不存在則輸出0。
【思路】最開始的思路是借助左程云老師的思路屎鳍，用一個cur和time來找出出現(xiàn)次數(shù)大于數(shù)組一半的字符宏娄，后來發(fā)現(xiàn)對于不存在的情況無法判斷，如{3,3,4,4,5}還是會輸出5逮壁。故采用字典映射的方式來尋找出現(xiàn)次數(shù)大于一般的字符孵坚，同時記得邊界條件的判斷。
代碼：
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
n = len(numbers)
#邊界條件，元素只有一個時
if n ==1:
return numbers[0]
#以時間換空間卖宠，采用字典記錄每個數(shù)字的出現(xiàn)次數(shù)
dict_num = {}
#時間復(fù)雜度為O(n)
for i in range(0,n):
if numbers[i] in dict_num.keys():
dict_num[numbers[i]] +=1
if dict_num[numbers[i]]>n/2:
return numbers[i]
else: dict_num[numbers[i]] = 1
return 0
