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

前言

前文传送门：

Python数据结构与算法刷题（1）——害死人不偿命的（3n+1）猜想

Python数据结构与算法刷题（2）——挖掘机技术哪家强

Python数据结构与算法刷题（3）——跟奥巴马一起学编程

Python数据结构与算法刷题（4）——D进制的A+B

Python数据结构与算法刷题（5）——回文串

这是一个腾讯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，即找不到超过一半数量的数字~

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

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

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

小编推荐一个最近刚出的正在打折促销的网络爬虫好课（往下看）

扫码下图或点击阅读原文即可试听学习

点击

阅读原文

，即可免费试听学习！