C++_Unordered_Map + Heap_65ms_80.89%


  • 0

    Update 12/15/2016: 65ms, 80.89%
    Because we use vector to store the tweets of one certain user, so these tweets are sorted from oldest to newest, so our question converted to be like find out the top 10 elements in N sorted vectors.

    Of course, we will use heap. The heap is sorted by the last unused element in all tweets. Each time we get the top element in our heap, and then use a pointer to indicate current "end" position of this vector, and then update the element information and push it back to our heap, which could also update our heap information.

    class compare{
    public:
    bool operator() (pair<vector<pair<int,int>>*, int> a,     pair<vector<pair<int,int>>*, int> b){
      return a.first->at(a.second).second < b.first->at(b.second).second;
     }
     };
    
    class Twitter {
    unordered_map<int, unordered_set<int>> UserId_follow;//UserId - follows
    unordered_map<int, vector<pair<int,int>>> UserId_tweet;// UserId, post a twitter, tweetId+time
    int Time = 1;
    public:
    /** Initialize your data structure here. */
    Twitter() {}
    void NewAccount(int userId){
        vector<pair<int,int>> st;
        unordered_set<int> st2;
        st2.insert(userId);
        UserId_tweet[userId] = st;
        UserId_follow[userId] = st2;
    }
    
    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        if(UserId_tweet.find(userId) == UserId_tweet.end()){
            NewAccount(userId);
        }
        UserId_tweet[userId].push_back({tweetId, Time});
        Time++;
    }
    
    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    vector<int> getNewsFeed(int userId) {
        if(UserId_tweet.find(userId) == UserId_tweet.end()) return {};
        priority_queue<pair<vector<pair<int,int>>*, int>, vector<pair<vector<pair<int,int>>*, int>>, compare> PQ;
        for(auto id : UserId_follow[userId]){
            if(UserId_tweet[id].empty()) continue;
            vector<pair<int,int>>* tmp = &UserId_tweet[id];
            PQ.push({tmp, UserId_tweet[id].size()-1});
        }
        vector<int> res;
        while(res.size() < 10 && !PQ.empty()){
            auto tmp = PQ.top();
            PQ.pop();
            res.push_back(tmp.first->at(tmp.second).first);
            if(tmp.second--){//recover
                PQ.push(tmp);
            }
        }
        return res;
    }
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        if(UserId_tweet.find(followerId) == UserId_tweet.end()) NewAccount(followerId);
        if(UserId_tweet.find(followeeId) == UserId_tweet.end()) NewAccount(followeeId);
        UserId_follow[followerId].insert(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        int k = 0;
        if(UserId_tweet.find(followerId) == UserId_tweet.end()) {NewAccount(followerId); k = 1;}
        if(followerId == followeeId) return;
        
        if(UserId_tweet.find(followeeId) == UserId_tweet.end()) {NewAccount(followeeId);}
        if(k == 1) return;//because we newly added this userId.
        if(UserId_follow[followerId].find(followeeId) == UserId_follow[followerId].end()) return;
        UserId_follow[followerId].erase(followeeId);
    }
    };
    

    0_1481842423023_99E1D0A8-3218-47CD-8910-7E9B34A450BE.png


    I am wondering that is there any more efficient algorithms for accounting the top 10 tweets for some certain user?

    class compare{
    public:
    bool operator() (pair<int,int> a, pair<int,int> b){
      return a.second < b.second;
    }
    };
    class Twitter {
    unordered_map<int, unordered_set<int>> UserId_follow;//UserId - follows
    unordered_map<int, vector<pair<int,int>>> UserId_tweet;// UserId, post a twitter
    int Time = 1;
     public:
    /** Initialize your data structure here. */
    Twitter() {
        
    }
    void NewAccount(int userId){
        vector<pair<int,int>> st;
        unordered_set<int> st2;
        st2.insert(userId);
        UserId_tweet[userId] = st;
        UserId_follow[userId] = st2;
    }
    
    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        if(UserId_tweet.find(userId) == UserId_tweet.end()){
            NewAccount(userId);
        }
        UserId_tweet[userId].push_back({tweetId, Time});
        Time++;
    }
    
    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    vector<int> getNewsFeed(int userId) {
        if(UserId_tweet.find(userId) == UserId_tweet.end()) return {};
        priority_queue<pair<int,int>, vector<pair<int,int>>, compare> PQ;
        for(auto id : UserId_follow[userId]){
            if(UserId_tweet[id].empty()) continue;
            for(auto tweet : UserId_tweet[id]){
                PQ.push(tweet);
                if(PQ.size() > 10) PQ.pop();
            }
        }
        int cnt = PQ.size() > 10 ? 10 : PQ.size();
        vector<int> res(cnt);
        while(cnt >= 0 && !PQ.empty()){
            res[--cnt] = (PQ.top().first);
            PQ.pop();
        }
        return res;
    }
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        if(UserId_tweet.find(followerId) == UserId_tweet.end()) NewAccount(followerId);
        if(UserId_tweet.find(followeeId) == UserId_tweet.end()) NewAccount(followeeId);
        UserId_follow[followerId].insert(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        int k = 0;
        if(UserId_tweet.find(followerId) == UserId_tweet.end()) {NewAccount(followerId); k = 1;}
        if(followerId == followeeId) return;//you cannot follow yourself!
        
        if(UserId_tweet.find(followeeId) == UserId_tweet.end()) {NewAccount(followeeId);}
        if(k == 1) return;//because we newly added this userId.
        if(UserId_follow[followerId].find(followeeId) == UserId_follow[followerId].end()) return;
        UserId_follow[followerId].erase(followeeId);
    }
    };

Log in to reply
 

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