题目描述

设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：

1. postTweet(userId, tweetId): 创建一条新的推文
2. getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
3. follow(followerId, followeeId): 关注一个用户
4. unfollow(followerId, followeeId): 取消关注一个用户

样例

Twitter twitter = new Twitter();

// 用户1发送了一条新推文 (用户id = 1, 推文id = 5).
twitter.postTweet(1, 5);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
twitter.getNewsFeed(1);

// 用户1关注了用户2.
twitter.follow(1, 2);

// 用户2发送了一个新推文 (推文id = 6).
twitter.postTweet(2, 6);

// 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5].
// 推文id6应当在推文id5之前，因为它是在5之后发送的.
twitter.getNewsFeed(1);

// 用户1取消关注了用户2.
twitter.unfollow(1, 2);

// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
// 因为用户1已经不再关注用户2.
twitter.getNewsFeed(1);

算法

(哈希表+堆)

这道题可以看成是一个面向对象设计 (OOD) 的题目，我们需要实现四个操作，关注一个用户，取关一个用户，发表一条推特，和获取新闻流。

对于关注和取关用户的操作，我们自然想到对一个用户的关注列表我们可以维护一个哈希表unordered_set来做到常数时间的操作，并且可以控制重复关注某个用户等等无效操作。那么对于多个用户我们同样可以利用哈希表unordered_map<int, unordered_set<int>>来维护每个用户的关注列表。

由于在发表推特的时候我们需要带上一个时间戳以及推文id，我们可以设计一个推文结构体struct Tweet，其中时间戳可以用一个全局的UUID来实现，每当一个用户发表一条推文后我们就让它自增一，这里因为不涉及到并发以及分布式处理，所以不会出现多个推文使用同一个UUID的情况。同样的我们可以用哈希表unordered_map<int, list<Tweet>>来存储每个用户的推文列表，每当一个用户发表一条新推文时我们就将它插入到列表首部，这样对每个用户而言，推文列表就是按时间降序排列的了。

接下来我们需要设计获取新闻流的功能，由于在之前的设计中每个用户的推文列表已经是按时间排好序的，所以我们可以利用归并排序的思想，将该用户以及该用户关注的所有用户的推文列表取出，将它们的头结点放入一个堆中，每次取出时间最近的推文，然后将该推文在对应列表中的下一个推文放入堆中，直到堆为空或者已经取到了十条推文为止。由于我们在堆中取出元素后还需要将它在列表中的下一个元素放入堆中，这可以利用迭代器来实现，所以我们可以定义一个结构体struct Feed，里面存放两个迭代器list<Tweet>::iterator分别指向推文列表的起点和终点，这样我们对每个用户只用在堆中放入一个Feed就好了。

注意这里每个用户的关注列表里不能有他自己，不然我们在获取新闻流时就会重复计算该用户的推文列表。

时间复杂度

关注和取关用户以及发推特的复杂度都是 $O(1)$，获取新闻流的复杂度为 $O(10\log k)$，这里 $k$ 为该用户关注的总用户数。

C++ 代码

class Twitter {
public:
    struct Tweet {
        int tweetId, time;
    };

    struct Feed {
        list<Tweet>::iterator cur, end;
        bool operator<(const Feed& other) const {
            return (*cur).time < (*other.cur).time;
        }
    };

    int id;
    unordered_map<int, list<Tweet>> tweets;
    unordered_map<int, unordered_set<int>> follows;

    /** Initialize your data structure here. */
    Twitter() {
        id = 0;
    }

    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        tweets[userId].push_front({tweetId, id ++ });
    }

    /** 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) {
        priority_queue<Feed> pq;
        if (tweets[userId].size())
            pq.push({tweets[userId].begin(), tweets[userId].end()});
        for (auto user : follows[userId])
            if (tweets[user].size())
                pq.push({tweets[user].begin(), tweets[user].end()});
        vector<int> res;

        while (res.size() < 10 && pq.size()) {
            auto t = pq.top();
            res.push_back((*t.cur).tweetId);
            pq.pop();
            if (++ t.cur != t.end) pq.push(t);
        }

        return res;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        follows[followerId].insert(followeeId);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        if (!follows.count(followerId)) return;
        follows[followerId].erase(followeeId);
    }
};

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter* obj = new Twitter();
 * obj->postTweet(userId,tweetId);
 * vector<int> param_2 = obj->getNewsFeed(userId);
 * obj->follow(followerId,followeeId);
 * obj->unfollow(followerId,followeeId);
 */