LeetCode 355 Design Twitter

    
        标签：
        
            设计数据结构
        
            LeetCode
        
    发布于：2022-02-11 00:03:30
    编辑于：2022-02-11 12:45:56
    浏览量：806

概述

https://leetcode.com/problems/design-twitter/

需要我们存储的信息：

用户之间的关注关系，显然这是一个图；
用户发的 tweet，我们需要记录前后顺序和发送者。

设用户个数为 m，tweet 个数为 n。

基于全局数组的解法

所有 tweet 存到一个向量里，需要获取 feed 的时候，就从末尾处按个遍历，直到凑够 10 个合适的或者到达末尾为之。

时间复杂度：getNewsFeed 操作最坏情况 O(n) 最好情况 O(1)，postTweet 操作 O(1) 空间复杂度：max(O(n), O(m^2))

const int MAX_USER_NUM = 501;

class Twitter {
public:
    vector<pair<int, int>> tweets;
    bool graph[MAX_USER_NUM][MAX_USER_NUM] = {0};
    Twitter() {
        for (int i = 0; i < MAX_USER_NUM; i ++) {
            graph[i][i] = true;
        }
    }
    
    void postTweet(int userId, int tweetId) {
        tweets.push_back({userId, tweetId});
    }
    
    vector<int> getNewsFeed(int userId) {
        vector<int> res;
        for (int i = tweets.size() - 1; i >= 0; i --) {
            if (graph[userId][tweets[i].first]) {
                res.push_back(tweets[i].second);
                if (res.size() == 10) break;
            }
        }
        return res;
    }
    
    void follow(int followerId, int followeeId) {
        graph[followerId][followeeId] = true;
    }
    
    void unfollow(int followerId, int followeeId) {
        graph[followerId][followeeId] = false;
    }
};

拉式（为每个用户维护发帖列表）

每个用户维护一个其发帖记录，于是我们的任务就是合并 f 个有序列表，且满 10 个就停，f 为其关注者数量。

getNewsFeed 时当场合并 feed。

时间复杂度：getNewsFeed 操作最坏情况 O(f)，postTweet 操作 O(1)
空间复杂度：max(O(n), O(m^2))

推式（为每个用户维护收贴列表）

每个用户额外维护一个大小为 10 的 queue，postTweet 直接遍历其所有关注者（记为 f）更新其 queue，另外这种情况下连用户关注关系图都不用了，~~但是为了取关时方便还是用吧~~，直接用 set 不就好了。

时间复杂度：getNewsFeed 操作 O(1)，postTweet 操作 O(f)
空间复杂度：O(n)

实际应用中我感觉是选 2，因为 2 的 getNewsFeed 操作是 O(1)，用户体验好，缺点是 feed 有一定延时，不过这种场景下还 okay。

这里我们实现后者。

这个思路虽然高效但确是错误的，因为这样的话用户没办法看关注前的帖子，也没办法在取关后从 feed 里剔除掉帖子。

后者还好说，但是前者难搞。

class Twitter {
public:
    vector<pair<int, int>> tweets;
    unordered_map<int, set<int>> user2followers;
    unordered_map<int, list<int>> user2feeds;
    Twitter() {
    }
    
    void postTweet(int userId, int tweetId) {
        tweets.push_back({userId, tweetId});
        if (user2followers.count(userId)) {
            user2followers[userId].insert(userId);
        }
        for (auto i : user2followers[userId]) {
            user2feeds[i].push_front(tweetId);
            if (user2feeds[i].size() > 10) user2feeds[i].pop_back();
        }
    }
    
    vector<int> getNewsFeed(int userId) {
        vector<int> res(user2feeds[userId].begin(), user2feeds[userId].end());
        return res;
    }
    
    void follow(int followerId, int followeeId) {
        user2followers[followeeId].insert(followerId);
    }
    
    void unfollow(int followerId, int followeeId) {
        user2followers[followeeId].erase(followerId);
    }
};

Links: leetcode-355-design-twitter