LeetCode 355 Design Twitter

Tag: 设计数据结构 LeetCode Posted on 2022-02-11 00:03:30 Edited on 2022-02-11 12:45:56 Views: 169

概述

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

需要我们存储的信息:

  1. 用户之间的关注关系,显然这是一个图;
  2. 用户发的 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);
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/