題目的內(nèi)容描述：

春節(jié)期間小明使用微信收到很多個(gè)紅包，非常開心。在查看領(lǐng)取紅包記錄時(shí)發(fā)現(xiàn)，某個(gè)紅包金額出現(xiàn)的次數(shù)超過了紅包總數(shù)的一半。請(qǐng)幫小明找到該紅包金額。寫出具體算法思路和代碼實(shí)現(xiàn)，要求算法盡可能高效。

給定一個(gè)紅包的金額數(shù)組gifts及它的大小n，請(qǐng)返回所求紅包的金額。若沒有金額超過總數(shù)的一半，返回0。

測(cè)試樣例：

[1，2，3，2，2]，5

返回：

2

思路：考慮到題目要求算法盡可能高效，所以放棄使用hashtable計(jì)數(shù)比較來做

使用相同則增一計(jì)數(shù)，相異則減一計(jì)數(shù)，設(shè)序列首部值為key，count = 1

然后從序列第二個(gè)值開始循環(huán)，每次循環(huán)元素與key比較，如果相同，則count++

不同則，count--，直到count變?yōu)?1，則考慮此時(shí)的元素為key，繼續(xù)從當(dāng)前位置循環(huán)直到序列結(jié)束

需要其他的大型互聯(lián)公司面試題目的朋友可以關(guān)注小編后私信領(lǐng)取

例子如下：

例如 4 4 2 3 4

首先，key = 4 ，count = 1，第二個(gè)4與key相同，count增加1，變?yōu)?

然后2 3分別與key不同，count減去2，變?yōu)?

最后4與key相同，count++，變?yōu)?

輸出結(jié)果是4

這樣看起來好像沒什么問題，但是如果出現(xiàn)以下情況呢？

例如 4 4 4 3 3 2 2 1 1

首先key = 4 ，count為1，經(jīng)過另外兩個(gè)4，key還是4，count變?yōu)?

經(jīng)過 3 3 2 ，key為4，count為0

接著經(jīng)過2 ，key為4，count為-1，此時(shí)考慮變換key為2，count為1

接著經(jīng)過1，key為2，count為0

接著經(jīng)過1，key為2，count為-1，此時(shí)考慮變換key為1，count為1

所以結(jié)果是1

但是這個(gè)序列里1明顯不是超過一半的

這是為什么呢？因?yàn)樵谶@有點(diǎn)像 鷸蚌相爭(zhēng)漁翁得利，4 3 2分別爭(zhēng)寵，最后1收了漁網(wǎng)~

那怎么避免呢？

在第一次循環(huán)后將最后的key再次帶入第二次循環(huán)，和序列元素比較

為了區(qū)別count，使用flag作為計(jì)數(shù)器，初始化為1

當(dāng)遍歷序列時(shí)，相同則flag++，不同則flag--

當(dāng)序列比較結(jié)束，看flag是否大于等于1，如果是，則超過一半，輸出key

如果不是，輸出None

代碼實(shí)現(xiàn)如下：

（gifts用list相關(guān)名稱表示）

多個(gè)測(cè)試數(shù)據(jù)：

注意list_4 調(diào)用函數(shù)返回值0，即找不到超過一半數(shù)量的數(shù)字~