355. 设计推特

Medium

题目描述

设计一个简化版的推特，用户可以发布推文，关注/取消关注其他用户，并能够在新闻推送中看到最近的 10 条推文。

实现 Twitter 类：

Twitter() 初始化你的推特对象。
void postTweet(int userId, int tweetId) 用户 userId 发布一条新推文，推文 ID 为 tweetId。每次调用此函数都会使用一个唯一的 tweetId。
List<Integer> getNewsFeed(int userId) 检索用户 userId 新闻推送中最近的 10 条推文 ID。新闻推送中的每个项目都必须是用户关注的用户或者是用户自己发布的推文。推文必须按照从最近到最早的时间顺序进行排序。
void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。
void unfollow(int followerId, int followeeId) ID 为 followerId 的用户开始取消关注 ID 为 followeeId 的用户。

示例 1：

输入
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
输出
[null, null, [5], null, null, [6, 5], null, [5]]

解释
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // 用户 1 发布了一条新推文 (用户 id = 1, 推文 id = 5)
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
twitter.follow(1, 2);    // 用户 1 关注了用户 2
twitter.postTweet(2, 6); // 用户 2 发布了一个新推文 (用户 id = 2, 推文 id = 6)
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5]。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的
twitter.unfollow(1, 2);  // 用户 1 取消关注了用户 2
twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2

提示：

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 10^4
所有推文都有不同的 ID
postTweet、getNewsFeed、follow 和 unfollow 方法最多调用 3 * 10^4 次
用户不能关注自己

解题思路

这道题需要设计一个推特系统，涉及多个数据结构的组合使用。

核心思路：

推文存储：使用哈希表存储每个用户的推文列表，按发布时间顺序保存
关注关系：使用哈希表存储用户的关注列表
时间戳：为每条推文分配全局递增的时间戳，便于排序
新闻推送：合并用户自己和关注用户的推文，按时间排序后返回最新的10条

具体实现：

使用 timestamp 变量为每条推文分配唯一的时间戳
tweets 哈希表存储用户ID到推文列表的映射，每个推文包含ID和时间戳
following 哈希表存储用户的关注关系
getNewsFeed 方法中，收集用户自己和关注用户的所有推文，按时间戳排序后返回前10条

优化点：

可以为每个用户只保存最近的推文，避免内存浪费
使用优先队列（堆）可以更高效地获取最新的k条推文

代码实现

class Twitter {
private:
    int timestamp;
    unordered_map<int, vector<pair<int, int>>> tweets; // userId -> [(tweetId, time)]
    unordered_map<int, unordered_set<int>> following; // userId -> set of followeeId
    
public:
    Twitter() {
        timestamp = 0;
    }
    
    void postTweet(int userId, int tweetId) {
        tweets[userId].push_back({tweetId, timestamp++});
    }
    
    vector<int> getNewsFeed(int userId) {
        vector<pair<int, int>> allTweets;
        
        // Add user's own tweets
        if (tweets.count(userId)) {
            for (auto& tweet : tweets[userId]) {
                allTweets.push_back(tweet);
            }
        }
        
        // Add followed users' tweets
        if (following.count(userId)) {
            for (int followeeId : following[userId]) {
                if (tweets.count(followeeId)) {
                    for (auto& tweet : tweets[followeeId]) {
                        allTweets.push_back(tweet);
                    }
                }
            }
        }
        
        // Sort by timestamp in descending order
        sort(allTweets.begin(), allTweets.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;
        });
        
        vector<int> result;
        for (int i = 0; i < min(10, (int)allTweets.size()); i++) {
            result.push_back(allTweets[i].first);
        }
        
        return result;
    }
    
    void follow(int followerId, int followeeId) {
        if (followerId != followeeId) {
            following[followerId].insert(followeeId);
        }
    }
    
    void unfollow(int followerId, int followeeId) {
        if (following.count(followerId)) {
            following[followerId].erase(followeeId);
        }
    }
};

class Twitter:

    def __init__(self):
        self.timestamp = 0
        self.tweets = {}  # userId -> [(tweetId, time)]
        self.following = {}  # userId -> set of followeeId

    def postTweet(self, userId: int, tweetId: int) -> None:
        if userId not in self.tweets:
            self.tweets[userId] = []
        self.tweets[userId].append((tweetId, self.timestamp))
        self.timestamp += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        all_tweets = []
        
        # Add user's own tweets
        if userId in self.tweets:
            all_tweets.extend(self.tweets[userId])
        
        # Add followed users' tweets
        if userId in self.following:
            for followee_id in self.following[userId]:
                if followee_id in self.tweets:
                    all_tweets.extend(self.tweets[followee_id])
        
        # Sort by timestamp in descending order and return top 10
        all_tweets.sort(key=lambda x: x[1], reverse=True)
        return [tweet[0] for tweet in all_tweets[:10]]

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            if followerId not in self.following:
                self.following[followerId] = set()
            self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId in self.following and followeeId in self.following[followerId]:
            self.following[followerId].remove(followeeId)

public class Twitter {
    private int timestamp;
    private Dictionary<int, List<(int tweetId, int time)>> tweets;
    private Dictionary<int, HashSet<int>> following;

    public Twitter() {
        timestamp = 0;
        tweets = new Dictionary<int, List<(int, int)>>();
        following = new Dictionary<int, HashSet<int>>();
    }
    
    public void PostTweet(int userId, int tweetId) {
        if (!tweets.ContainsKey(userId)) {
            tweets[userId] = new List<(int, int)>();
        }
        tweets[userId].Add((tweetId, timestamp++));
    }
    
    public IList<int> GetNewsFeed(int userId) {
        var allTweets = new List<(int tweetId, int time)>();
        
        // Add user's own tweets
        if (tweets.ContainsKey(userId)) {
            allTweets.AddRange(tweets[userId]);
        }
        
        // Add followed users' tweets
        if (following.ContainsKey(userId)) {
            foreach (int followeeId in following[userId]) {
                if (tweets.ContainsKey(followeeId)) {
                    allTweets.AddRange(tweets[followeeId]);
                }
            }
        }
        
        // Sort by timestamp in descending order
        allTweets.Sort((a, b) => b.time.CompareTo(a.time));
        
        var result = new List<int>();
        for (int i = 0; i < Math.Min(10, allTweets.Count); i++) {
            result.Add(allTweets[i].tweetId);
        }
        
        return result;
    }
    
    public void Follow(int followerId, int followeeId) {
        if (followerId != followeeId) {
            if (!following.ContainsKey(followerId)) {
                following[followerId] = new HashSet<int>();
            }
            following[followerId].Add(followeeId);
        }
    }
    
    public void Unfollow(int followerId, int followeeId) {
        if (following.ContainsKey(followerId)) {
            following[followerId].Remove(followeeId);
        }
    }
}

var Twitter = function() {
    this.timestamp = 0;
    this.tweets = new Map(); // userId -> [{tweetId, time}]
    this.following = new Map(); // userId -> Set of followeeId
};

Twitter.prototype.postTweet = function(userId, tweetId) {
    if (!this.tweets.has(userId)) {
        this.tweets.set(userId, []);
    }
    this.tweets.get(userId).push({tweetId: tweetId, time: this.timestamp++});
};

Twitter.prototype.getNewsFeed = function(userId) {
    let allTweets = [];
    
    // Add user's own tweets
    if (this.tweets.has(userId)) {
        allTweets.push(...this.tweets.get(userId));
    }
    
    // Add followed users' tweets
    if (this.following.has(userId)) {
        for (let followeeId of this.following.get(userId)) {
            if (this.tweets.has(followeeId)) {
                allTweets.push(...this.tweets.get(followeeId));
            }
        }
    }
    
    // Sort by timestamp in descending order and return top 10
    allTweets.sort((a, b) => b.time - a.time);
    return allTweets.slice(0, 10).map(tweet => tweet.tweetId);
};

Twitter.prototype.follow = function(followerId, followeeId) {
    if (followerId !== followeeId) {
        if (!this.following.has(followerId)) {
            this.following.set(followerId, new Set());
        }
        this.following.get(followerId).add(followeeId);
    }
};

Twitter.prototype.unfollow = function(followerId, followeeId) {
    if (this.following.has(followerId)) {
        this.following.get(followerId).delete(followeeId);
    }
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
postTweet	O(1)	O(1)
getNewsFeed	O(T log T)	O(T)
follow	O(1)	O(1)
unfollow	O(1)	O(1)

其中 T 是用户及其关注用户的总推文数量。在最坏情况下，T 可能达到所有用户的推文总数。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目