前言
前文传送门：
Python数据结构与算法刷题（1）——害死人不偿命的（3n+1）猜想
这是一个腾讯2016招聘笔试题：
题目来源：http://group.jobbole.com/30876/#comm-91845
题目描述
春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
给定一个红包的金额数组gifts及它的大小n，请返回所求红包的金额。
若没有金额超过总数的一半，返回0。
测试样例：
[1，2，3，2，2]，5
返回：
2
思路：考虑到题目要求算法尽可能高效，所以放弃使用hashtable计数比较来做
使用相同则增一计数，相异则减一计数，设序列首部值为key，count = 1
然后从序列第二个值开始循环，每次循环元素与key比较，如果相同，则count++
不同则，count--，直到count变为-1，则考虑此时的元素为key，继续从当前位置循环直到序列结束
例子如下：
例如 4 4 2 3 4
首先，key = 4 ，count = 1，第二个4与key相同，count增加1，变为2
然后2 3分别与key不同，count减去2，变为0
最后4与key相同，count++，变为1
输出结果是4
这样看起来好像没什么问题，但是如果出现以下情况呢？
例如 4 4 4 3 3 2 2 1 1
首先key = 4 ，count为1，经过另外两个4，key还是4，count变为3
经过 3 3 2 ，key为4，count为0
接着经过2 ，key为4，count为-1，此时考虑变换key为2，count为1
接着经过1，key为2，count为0
接着经过1，key为2，count为-1，此时考虑变换key为1，count为1
所以结果是1
但是这个序列里1明显不是超过一半的
这是为什么呢？因为在这有点像 鹬蚌相争渔翁得利，4 3 2分别争宠，最后1收了渔网~
那怎么避免呢？
在第一次循环后将最后的key再次带入第二次循环，和序列元素比较
为了区别count，使用flag作为计数器，初始化为1
当遍历序列时，相同则flag++，不同则flag--
当序列比较结束，看flag是否大于等于1，如果是，则超过一半，输出key
如果不是，输出None
代码实现如下：
（gifts用list相关名称表示）
多个测试数据：
注意list_4 调用函数返回值0，即找不到超过一半数量的数字~
这题有很多方法,你有更优化的方法么？
光看不练，眼高手低可不好哦，动手敲代码吧~
欢迎评论指出文中错误、代码优化和提问~~~
1 个评论
num = len(gitfs)
set_data = set(gits)
max = 0
money = 0
for i in set_data:
count = 0
for j in gits:
if i==j:
count += 1
if max < count:
max = count
money = i
if max > num / 2.0 :
return money
else:
return 0
gits = [1,3,3,2,2,3,3]
res = findRedBag(gits)
print(res)