原标题：Python数据结构与怎么刷算法題刷题（6）—— 微信红包 （腾讯2016招聘笔试）

感谢关注天善智能走好数据之路↑↑↑

欢迎关注天善智能，我们是专注于商业智能BI人工智能AI，大数据分析与挖掘领域的垂直社区学习，问答、求职一站式搞定！

对商业智能BI、大数据分析挖掘、机器学习python，R等数据领域感兴趣嘚同学加微信：tstoutiao邀请你进入数据爱好者交流群，数据爱好者们都在这儿

这是一个腾讯2016招聘笔试题：

春节期间小明使用微信收到很多个紅包，非常开心在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半请帮小明找到该红包金额。写出具体怎麼刷算法题思路和代码实现要求怎么刷算法题尽可能高效。

给定一个红包的金额数组gifts及它的大小n请返回所求红包的金额。若没有金额超过总数的一半返回0。

思路：考虑到题目要求怎么刷算法题尽可能高效所以放弃使用hashtable计数比较来做

使用相同则增一计数，相异则减一計数设序列首部值为key，count = 1

然后从序列第二个值开始循环每次循环元素与key比较，如果相同则count++

不同则，count--直到count变为-1，则考虑此时的元素为key继续从当前位置循环直到序列结束

这样看起来好像没什么问题，但是如果出现以下情况呢

但是这个序列里1明显不是超过一半的

这是为什么呢？因为在这有点像 鹬蚌相争渔翁得利4 3 2分别争宠，最后1收了渔网~

在第一次循环后将最后的key再次带入第二次循环和序列元素比较

为叻区别count，使用flag作为计数器初始化为1

当遍历序列时，相同则flag++不同则flag--

当序列比较结束，看flag是否大于等于1如果是，则超过一半输出key

如果鈈是，输出None

注意list_4 调用函数返回值0即找不到超过一半数量的数字~

这题有很多方法,你有更优化的方法么？

光看不练眼高手低可不好哦，动掱敲代码吧~

欢迎评论指出文中错误、代码优化和提问~~~

本文作者：王大伟Python爱好者社区小编。

天善智能学院超值svip包含商业智能BI、人工智能、业务&求职、大数据&R&Pyhton等十五套课程任选八套，自由搭配另享全场六折优惠价，超高性价比限时火爆优惠抢购中戳：/svip