O(klogn) solution with unordered_map and set


  • 0
    R
    class Solution {
    public:
        /*bool static cmp(pair<int,int> &a,pair<int,int> &b){
            if(a.second!=b.second)return a.second>b.second; else return a.first<b.first; 
        }*/
        vector<int> topKFrequent(vector<int>& A, int k) {
            set<pair<int,int>,greater<pair<int,int> > > st;
            unordered_map<int,int> mp;
            unordered_map<int,int>::iterator it;
            int n,i,j;
            n=A.size();
            for(i=0;i<n;i++){
                mp[A[i]]++;
            }
            vector<int> ans;
            /*vector<pair<int,int> > v(mp.begin(),mp.end());
            sort(v.begin(),v.end(),cmp);
            for(i=0;i<k;i++){
                ans.push_back(v[i].first);
            }*/
            for(it=mp.begin();it!=mp.end();it++){
                st.insert(make_pair(it->second,it->first));
            }
            set<pair<int,int>,greater<pair<int,int> > >::iterator t;
            for(i=1;i<=k;i++){
                t=st.begin();
                ans.push_back(t->second);
                st.erase(t);
            }
            return ans;
        }
    };//commented solution is with vector and explicit sorting

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.