Re: [閒聊] 每日leetcode

[enmeitiryous (enmeitiryous)]

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
→ sustainer123: 大師