Re: [問題] 不重複element的數量
※ 引述《kosodoro (kosodoro)》之銘言:
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: VC++ 2012
: 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
: 無
: 問題(Question):
: 假設我現在有多個vector<int>, 我想要計算這些vector中剛好出現一次的element的數量
: 例:{0,2,3,7},{1,3},{2,3,7}
: 答: 2(0和1)
: 目前想法是用unordered_map儲存每個element以及次數
: 然後再檢查剛好出現一次的element數量
: 不過這樣缺點是在insert完後還要再從頭檢查一次
: 想請教不知道有沒有更快的方法,謝謝!!
std::map<int, int/*dummy*/> cadidates;
std::map<int, int/*dummy*/> get_losts;
void TryInsert(int a)
{
if (get_losts.find(a) != get_losts.end())
{
return;
}
if (candidates.find(a) != candidates.end())
{
candidates.erase(a);
get_losts.insert(std::make_pair(a, -1);
return;
}
candidates.insert(a, -1);
}
最後candidates剩下的就是只出現一次的.
PS沒驗過complexity,
容器用map也只是偷懶,
(用vector + std::find也可以)(但可能比較慢?)
方法很爛, 拋磚引玉一下而已 XDD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.45.115
→
11/18 13:52, , 1F
11/18 13:52, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 2 篇):