C++ 69ms Solution with unordered_map and priority_queue Easy to understand and Concise


  • 0
    B
    class Twitter {
    private:
        unordered_map<int,unordered_set<int>> followed; 
        unordered_map<int,vector<pair<int,int>>> tweets;  //<userID<<order,tweetID>>> 
        int order;
    public:
        Twitter() {
            order = 0;   
        }
        void postTweet(int userId, int tweetId) {
            tweets[userId].push_back({order++,tweetId});
        }
        
        vector<int> getNewsFeed(int userId) {
            vector<int> ans;
            unordered_set<int> friends = followed[userId];
            friends.insert(userId);
            auto cmp = [](const pair<int, int>& a, const pair<int, int>& b){
                return a.first < b.first;
            };
            priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
            for(auto c:friends)
                for(auto d:tweets[c])
                    q.push(d);
            int n = 0;
            while(!q.empty() && n++<10){
                ans.push_back(q.top().second);
                q.pop();
            }
            return ans;
        }
        void follow(int followerId, int followeeId) {
            if(followed.count(followerId))
                followed[followerId].insert(followeeId);
            else{
                unordered_set<int> temp{followeeId};
                followed[followerId]= temp;
            }
        }
        void unfollow(int followerId, int followeeId) {
            followed[followerId].erase(followeeId);
        }
    };
    

    Finally get this right. The first version I wrote took whopping 389ms, The second one took 719ms. ROFL
    I got rid the map keyed by timestamp and used userId as key instead to make it more efficient.


Log in to reply
 

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