1、問題描述

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

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

測試樣例： [1,2,3,2,2],5
返回：2
2、問題思路 可以使用map統計每個紅包出現的次數：map<金額，次數> 用一個迭代器遍歷map：map<金額，次數>::iterator it 找出符合條件的紅包：返回 it->first
3、代碼具體實現
此方法不滿足時間復雜度N：O（N） #include <iostream> #include <map> #include <vector> #include <stdlib.h>using namespace std;int getValue(vector<int> gifts, int n) {if(gifts.empty() == true)return 0;map<int, int> gifts_count; for(int i = 0; i < n; i++) { gifts_count[gifts[i]]++; } map<int, int>::iterator it = gifts_count.begin();while(it != gifts_count.end()){if(it->second > n/2)return it->first;elseit++;}return 0; }void test() {int val[] = {1,2,3,2,2};vector<int> gifts(begin(val), end(val));int ret = getValue(gifts, gifts.size());if(ret != 0)cout<<"紅包：￥"<<ret<<" 出現次數超過一半"<<endl;elsecout<<"沒有紅包出現次數超過一半"<<endl; }

滿足時間復雜度：

int getValue(vector<int> gifts, int n) {int value = gifts[0];int count = 1;for(int i = 1; i < n; ++i){if(gifts[i] != value)--count;else++count;if(count == 0)value = gifts[i];}count = 0;for(int i = 0; i < n; ++i){if(gifts[i] == value)count++;}if(count < n/2)return 0;elsereturn value; }void test() {vector<int> gifts;gifts.push_back(1);gifts.push_back(2);gifts.push_back(3);gifts.push_back(2);gifts.push_back(2);cout<<getValue(gifts, 5)<<endl; }

總結

以上是生活随笔為你收集整理的微信红包问题：找出某个出现次数超过红包总数一半的红包的金额（面试题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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