Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/08/05 09:03)推噓0(0推 0噓 1→)留言1則, 1人參與討論串638/1548 (看更多)
2053 k-th distinct string
題目:
給你一個包含可能重複string的vector回傳只出現過一次且在這些只出現一次的string中
在原vector第k次出現的string，如果只出現一次的string不到k個則回傳空字串
思路:先用unordered map紀錄字串第幾個出現並有重複出現則記成-1，之後用map塞入
紀錄不為-1的字串，之後依序找到第k個字串並回傳，本來想說用nth element應該可以
壓在O(n)但想了下n<=1000，nlgn和n差不了多少就算了。
string kthDistinct(vector<string>& arr, int k) {
unordered_map<string,int> ff;
int cnt=1;
for(int i=0;i<arr.size();++i){
if(!ff.count(arr[i])){
ff[arr[i]]=i;
}
else{
ff[arr[i]]=-1;
}
}
map<int,string> dd;
for(auto ww:ff){
if(ww.second!=-1){
dd[ww.second]=ww.first;
}
}
for(auto e: dd){
if(cnt==k){
return e.second;
}
else{
cnt++;
}
}
return "";
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.16.83 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722819812.A.66B.html
→
08/05 09:59,
1年前
, 1F
08/05 09:59, 1F
討論串 (同標題文章)
完整討論串 (本文為第 638 之 1548 篇)：