題目描述

春節期間小明使用微信收到很多個紅包，非常開心。在查看領取紅包記錄時發現，某個紅包金額出現的次數超過了紅包總數的一半。請幫小明找到該紅包金額。寫出具體算法思路和代碼實現，要求算法盡可能高效。

給定一個紅包的金額數組gifts及它的大小n，請返回所求紅包的金額。

若沒有金額超過總數的一半，返回0。

測試樣例：

[1,2,3,2,2],5 返回：2

思路：常規方法這里不再贅述（n^2暴力，hash等），這里考慮采用巧妙的線性復雜度方法，我們通過兩個變量完成這項任務：

其中num表示一個數出現的次數，last表示當前這個數。因為我們知道一個數出現的次數大于總數的一半，則這個數有且僅有一個，因此我們通過當前數與last進行比較，若相等則num++，否則num--，若num=0，再更新last，則最后last的值一定是我們要的值。

class Gift { public:int getValue(vector<int> gifts, int n) {// write code hereint num=0,last;for(int i=0;i<n;i++){if(num==0){last=gifts[i];num=1;}else{if(last==gifts[i])num++;elsenum--;}}int size=0;for(int i=0;i<n;i++){if(last==gifts[i])size++;}return size>n/2?last:0;} };

?

總結

以上是生活随笔為你收集整理的腾讯历届笔试题（1）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。