感谢关注天善智能，走好数据之路↑↑↑
欢迎关注天善智能，我们是专注于商业智能BI，人工智能AI，大数据分析与挖掘领域的垂直社区，学习，问答、求职一站式搞定！
对商业智能BI、大数据分析挖掘、机器学习，python，R等数据领域感兴趣的同学加微信：tstoutiao，邀请你进入数据爱好者交流群，数据爱好者们都在这儿。
这是一个腾讯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爱好者社区小编。Hellobi Live | 1小时破冰入门Python
课程内容：
1、Anaconda安装
2、jupyter常用操作
3、Python基本数据类型
4、Python基本运算和表达式
5、Python程序基本控制流程（顺序，分支，循环）
6、Python特色数据类型（列表，元组，字典，集合）
7、Python函数
8、Python模块导入使用之time、random模块
9、Python异常处理
10、Python文件操作
11、Python后续学习提升方向和建议
天善智能学院超值svip，包含商业智能BI、人工智能、业务&求职、大数据&R&Pyhton等十五套课程任选八套，自由搭配，另享全场六折优惠价，超高性价比，限时火爆优惠抢购中戳：https://www.hellobi.com/svip
网友评论