绿色风格网站,可以看任何网站的浏览器下载,杭州百度首页优化,怎么网上注册公司1、问题描述 春节期间小明使用微信收到很多个红包#xff0c;非常开心。在查看领取红包记录时发现#xff0c;某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现#xff0c;要求算法尽可能高效。 给定一个红包的金额数组gif…1、问题描述 春节期间小明使用微信收到很多个红包非常开心。在查看领取红包记录时发现某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现要求算法尽可能高效。 给定一个红包的金额数组gifts及它的大小n请返回所求红包的金额。 测试样例[1,2,3,2,2],5返回22、问题思路可以使用map统计每个红包出现的次数map金额次数用一个迭代器遍历mapmap金额次数::iterator it找出符合条件的红包返回 it-first3、代码具体实现此方法不满足时间复杂度NON#include iostream
#include map
#include vector
#include stdlib.husing namespace std;int getValue(vectorint gifts, int n)
{if(gifts.empty() true)return 0;mapint, int gifts_count; for(int i 0; i n; i) { gifts_count[gifts[i]]; } mapint, 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};vectorint gifts(begin(val), end(val));int ret getValue(gifts, gifts.size());if(ret ! 0)cout红包ret 出现次数超过一半endl;elsecout没有红包出现次数超过一半endl;
}满足时间复杂度 int getValue(vectorint gifts, int n)
{int value gifts[0];int count 1;for(int i 1; i n; i){if(gifts[i] ! value)--count;elsecount;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()
{vectorint gifts;gifts.push_back(1);gifts.push_back(2);gifts.push_back(3);gifts.push_back(2);gifts.push_back(2);coutgetValue(gifts, 5)endl;
}
