题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路
- 第一步：记录数组中次数出现最多的个数
- 第二步：判断这个数是否出现次数超过一半
O(n)复杂度。
扩展问题
如果有且只有一个的出现最多的那个数字出现的次数是数组长度的一半呢？又或者是一半减1？ 我们还是继续从我们之前的那道超过一半的数来入手，我们的”阵地攻守”的解法是每遇到2个不同的数，就删除，剩下的就是那个出现次数超过一半的数字。
这个方法对于超过一半的情况可以成立，对于扩展问题就不再行得通了。
但是他们的本质是相同的，
- 对于一个长度为2n的数组，如果有个数出现次数超过n,那么至少有1组，连续2个数是重复的相应的，于是”阵地攻守”中每次不同的元素就删除（同归于尽）就可以找到那个元素
- 如果出现的次数为n, 那么至少有一组连续3个数是重复的。每3个不重复的数删除一次
- 如果是n-1, 就是一组至少有连续4个数重复。每4个不重复的数删除一次
def MoreThanHalfNum_Solution(numbers):
# write code here
res = None
cnt = 0
for i in numbers: # 留下数组中出现次数最高的数
if not res:
res = i
cnt = 1
else:
if i == res:
cnt += 1
else:
cnt -= 1
if cnt == 0:
res = None
# 判断次数是否大于一半
cnt = 0
for i in numbers:
if i == res:
cnt += 1
if cnt > len(numbers) / 2:
return res
else:
return 0
print(MoreThanHalfNum_Solution([1,2,3,2,2,2,5,4,2]))
