LeetCode 第355题：设计推特

📖 文章摘要

本文详细解析LeetCode第355题“设计推特”，这是一道设计类问题。文章提供了基于优先队列和哈希表的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升系统设计能力的读者。

核心知识点： 优先队列、哈希表、设计模式、数据结构 难度等级： 中等 推荐人群： 具有一定数据结构基础，想要提升系统设计能力的程序员

题目描述

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

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

示例

示例 1：

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);

提示

• 所有推文ID都是唯一的
• 用户ID是唯一的
• 用户不会关注自己
• 用户不会重复关注同一个用户
• 用户不会取消关注未关注的用户

解题思路

本题可以使用优先队列和哈希表来实现：

1. 使用哈希表存储用户关注列表
2. 使用哈希表存储用户推文列表
3. 使用优先队列获取最近的推文
4. 使用时间戳记录推文发送时间

时间复杂度：

• postTweet: O(1)
• getNewsFeed: O(n log k)，其中n是关注用户数，k是返回的推文数
• follow/unfollow: O(1)

空间复杂度： O(n + m)，其中n是用户数，m是推文数

图解思路

数据结构设计

组件	数据结构	用途
用户关注列表	HashMap<userId, Set>	存储用户关注的人
用户推文列表	HashMap<userId, List>	存储用户发送的推文
推文对象	自定义类	存储推文ID和时间戳

操作流程分析

操作	步骤	说明
发送推文	1. 获取用户推文列表 2. 添加新推文	O(1)时间复杂度
获取推文	1. 获取关注列表 2. 合并推文 3. 使用优先队列排序	O(n log k)时间复杂度
关注用户	1. 获取用户关注列表 2. 添加被关注者	O(1)时间复杂度
取消关注	1. 获取用户关注列表 2. 移除被关注者	O(1)时间复杂度

代码实现

C# 实现

public class Twitter {
    private class Tweet {
        public int Id { get; set; }
        public int Timestamp { get; set; }
        public Tweet(int id, int timestamp) {
            Id = id;
            Timestamp = timestamp;
        }
    }

    private Dictionary<int, HashSet<int>> followings;
    private Dictionary<int, List<Tweet>> tweets;
    private int timestamp;

    public Twitter() {
        followings = new Dictionary<int, HashSet<int>>();
        tweets = new Dictionary<int, List<Tweet>>();
        timestamp = 0;
    }

    public void PostTweet(int userId, int tweetId) {
        if (!tweets.ContainsKey(userId)) {
            tweets[userId] = new List<Tweet>();
        }
        tweets[userId].Add(new Tweet(tweetId, timestamp++));
    }

    public IList<int> GetNewsFeed(int userId) {
        var result = new List<int>();
        var pq = new PriorityQueue<Tweet, int>();
        
        // 添加自己的推文
        if (tweets.ContainsKey(userId)) {
            foreach (var tweet in tweets[userId]) {
                pq.Enqueue(tweet, -tweet.Timestamp);
            }
        }
        
        // 添加关注者的推文
        if (followings.ContainsKey(userId)) {
            foreach (var followeeId in followings[userId]) {
                if (tweets.ContainsKey(followeeId)) {
                    foreach (var tweet in tweets[followeeId]) {
                        pq.Enqueue(tweet, -tweet.Timestamp);
                    }
                }
            }
        }
        
        // 获取最近的10条推文
        while (pq.Count > 0 && result.Count < 10) {
            result.Add(pq.Dequeue().Id);
        }
        
        return result;
    }

    public void Follow(int followerId, int followeeId) {
        if (!followings.ContainsKey(followerId)) {
            followings[followerId] = new HashSet<int>();
        }
        followings[followerId].Add(followeeId);
    }

    public void Unfollow(int followerId, int followeeId) {
        if (followings.ContainsKey(followerId)) {
            followings[followerId].Remove(followeeId);
        }
    }
}

Python 实现

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.followings = defaultdict(set)
        self.tweets = defaultdict(list)
        self.timestamp = 0

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

    def getNewsFeed(self, userId: int) -> List[int]:
        # 获取所有相关推文
        tweets = []
        # 添加自己的推文
        tweets.extend(self.tweets[userId])
        # 添加关注者的推文
        for followeeId in self.followings[userId]:
            tweets.extend(self.tweets[followeeId])
        
        # 使用堆排序获取最近的10条推文
        return [tweetId for _, tweetId in heapq.nlargest(10, tweets)]

    def follow(self, followerId: int, followeeId: int) -> None:
        self.followings[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.followings[followerId].discard(followeeId)

C++ 实现

class Twitter {
private:
    struct Tweet {
        int id;
        int timestamp;
        Tweet(int id, int timestamp) : id(id), timestamp(timestamp) {}
    };
    
    unordered_map<int, unordered_set<int>> followings;
    unordered_map<int, vector<Tweet>> tweets;
    int timestamp;

public:
    Twitter() : timestamp(0) {}
    
    void postTweet(int userId, int tweetId) {
        tweets[userId].emplace_back(tweetId, timestamp++);
    }
    
    vector<int> getNewsFeed(int userId) {
        vector<int> result;
        priority_queue<pair<int, int>> pq;
        
        // 添加自己的推文
        for (const auto& tweet : tweets[userId]) {
            pq.push({tweet.timestamp, tweet.id});
        }
        
        // 添加关注者的推文
        for (int followeeId : followings[userId]) {
            for (const auto& tweet : tweets[followeeId]) {
                pq.push({tweet.timestamp, tweet.id});
            }
        }
        
        // 获取最近的10条推文
        while (!pq.empty() && result.size() < 10) {
            result.push_back(pq.top().second);
            pq.pop();
        }
        
        return result;
    }
    
    void follow(int followerId, int followeeId) {
        followings[followerId].insert(followeeId);
    }
    
    void unfollow(int followerId, int followeeId) {
        followings[followerId].erase(followeeId);
    }
};

执行结果

C# 实现

• 执行用时：156 ms
• 内存消耗：45.2 MB

Python 实现

• 执行用时：32 ms
• 内存消耗：16.4 MB

C++ 实现

• 执行用时：0 ms
• 内存消耗：7.2 MB

性能对比

语言	执行用时	内存消耗	特点
C++	0 ms	7.2 MB	执行效率最高，内存占用最小
Python	32 ms	16.4 MB	代码简洁，易于理解
C#	156 ms	45.2 MB	类型安全，内存占用较大

代码亮点

1. 🎯 使用优先队列高效获取最近推文
2. 💡 采用时间戳记录推文顺序
3. 🔍 合理使用哈希表存储用户关系
4. 🎨 代码结构清晰，易于维护

常见错误分析

1. 🚫 未考虑用户不存在的情况
2. 🚫 推文排序逻辑错误
3. 🚫 内存使用效率低下
4. 🚫 未处理并发访问问题

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
优先队列	O(n log k)	O(n + m)	高效获取最近推文	需要额外排序时间
链表存储	O(n)	O(n + m)	按时间顺序存储	获取最近推文效率低

相关题目

• LeetCode 380. O(1) 时间插入、删除和获取随机元素 - 中等
• LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复 - 困难
• LeetCode 432. 全 O(1) 的数据结构 - 困难

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第355题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！