定义：给定N个数，出现次数最多的数为众数，若某众数出现次数大于N/2，则称其为绝对众数
已知给定N个整数存在绝对众数，以最低的时空复杂度计算该绝对众数。O(N)
算法分析：删除数组A中两个不同的数，绝对众数不变！！！
- 若两个数中有一个是绝对众数，则剩余的N-2个数中，绝对众数仍然大于(N-2)/2
- 若两个数中没有绝对众数，显然不影响绝对众数
# !/usr/bin/env python
# -- coding: utf-8 --
# @Time : 2017/7/18 21:57
# @Author : Albert·Sun
# @Version : 0.10α-β
# @Description : 寻找绝对众数
def absult_Much(arr):
times = 0
much_n = arr[0]
for i in range(len(arr)):
if times == 0: # 暂以当前数为众数
much_n = arr[i]
times += 1
elif arr[i] == much_n: # 次数加1
times += 1
else: # 次数减一，等价于删除一次众数和另一个数
times -= 1
return much_n
if __name__ == "__main__":
arr = [2, 1, 1, 3, 2, 1, 2, 1, 1]
print absult_Much(arr)
