技术 | Python从零开始系列连载（二十六）
导读
为了解答大家学习Python时遇到各种常见问题，小灯塔特地整理了一系列从零开始的入门到熟练的系列连载，每周五准时推出，欢迎大家学积极学习转载~
在上一期的Python数据结构与算法刷题模块，我们已经学会了回文串，今天就让我们一起进入下一节吧！Python的基础和进阶知识的连载欢迎到文末处查看往期精彩文章，也可以在菜单栏【Python连载】查看！
微信红包
这是一个腾讯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，即找不到超过一半数量的数字~
这题有很多方法,你有更优化的方法么？
光看不练，眼高手低可不好哦，动手敲代码吧~
欢迎评论指出文中错误、代码优化和提问~~~
好啦，这期的分享先到这里，大家可以按照上面的详细步骤进行练习。加油，我们下周五不见不散~
文章来源：Python爱好者社区
文章编辑：小雨