0355. Design Twitter

题目信息

题号:

0355

难度:

Medium

主题:

设计、社交关系、时间顺序、对象状态

原题:

LeetCode 0355

重点:

新闻流包含本人和关注者推文、最多返回十条、按发布时间倒序、关注关系与推文跨调用保存

题目重述

实现 Twitter 类,支持以下操作:postTweet(userId, tweetId) 由指定用户发布一条推文;getNewsFeed(userId) 返回该用户本人及其当前关注对象发布的最近最多十条推文编号;follow(followerId, followeeId) 建立关注关系;unfollow(followerId, followeeId) 取消关注关系。

新闻流必须按发布时间从新到旧排列,而不是按推文编号排序。用户始终可以看到自己的推文,无需关注自己;取消一条不存在的关注关系不会产生额外效果。用户编号、关注双方编号位于 [1, 500],推文编号位于 [0, 10^4] 且每条推文编号唯一,对对象的调用总数不超过 3 * 10^4。同一对象必须持续保存所有推文时间顺序和当前关注关系。

自建示例

关注关系改变新闻流:

调用:postTweet(1, 20), postTweet(2, 31), follow(1, 2), getNewsFeed(1)
输出:[31,20]
解释:用户 1 关注用户 2 后,新闻流同时包含双方推文;31 发布得更晚,所以排在 20 前面。

取消关注只移除对方推文:

调用:unfollow(1, 2), postTweet(1, 44), getNewsFeed(1)
输出:[44,20]
解释:用户 2 的推文不再进入用户 1 的新闻流,用户 1 自己的新旧推文仍按时间倒序保留。

按用户保存推文,再合并各来源的最新位置

每个用户的推文按发布时间递增保存,关注关系用集合保存。查询用户的新闻流时,来源是“用户自己加当前关注者”;对每个来源先把其最后一条推文放入最大堆,堆顶就是所有来源中最新的一条。弹出一条后,只把同一用户的上一条推文放回堆,重复最多十次即可得到全局最新十条。

堆中记录用户和该用户推文数组中的位置,而不是只记录推文编号;这样即使编号大小与发布时间无关,也能始终按时间排序。关注或取消关注只改变集合,历史推文不需要搬移。

C++ 实现

class Twitter {
    struct Tweet {
        long long time;
        int id;
    };

    struct Node {
        long long time;
        int user;
        int index;
        int id;

        bool operator<(const Node& other) const {
            return time < other.time;
        }
    };

    long long clock = 0;
    std::vector<Tweet> tweets[501];
    std::unordered_set<int> following[501];

public:
    void postTweet(int userId, int tweetId) {
        tweets[userId].push_back({clock++, tweetId});
    }

    std::vector<int> getNewsFeed(int userId) {
        std::unordered_set<int> sources = following[userId];
        sources.insert(userId);

        std::priority_queue<Node> queue;
        for (int source : sources) {
            if (tweets[source].empty()) continue;
            int index = static_cast<int>(tweets[source].size()) - 1;
            const Tweet& tweet = tweets[source][index];
            queue.push({tweet.time, source, index, tweet.id});
        }

        std::vector<int> result;
        while (!queue.empty() && result.size() < 10) {
            Node current = queue.top();
            queue.pop();
            result.push_back(current.id);
            if (current.index == 0) continue;

            int previous = current.index - 1;
            const Tweet& tweet = tweets[current.user][previous];
            queue.push({tweet.time, current.user,
                        previous, tweet.id});
        }
        return result;
    }

    void follow(int followerId, int followeeId) {
        following[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        following[followerId].erase(followeeId);
    }
};

代码分析

每个来源只把一条“当前候选”放入堆,弹出后再补该来源的上一条,因此不会漏掉时间更早但仍可能进入前十的推文;用集合并入本人也避免关注自己造成重复来源。若有 u 个来源,查询成本约为 O((u + 10) log u),发布和关系修改为平均 O(1),历史推文与关注关系占 O(T + F) 空间。