摘要

在社交媒体平台里，推送机制是核心功能之一。比如你关注了某人，就希望在自己的时间线上能看到他们的最新消息，同时自己的消息也要能出现在别人的首页。LeetCode 355 题——“设计推特”就把这个场景简化成一个核心设计题。我们要实现一个小型 Twitter 系统，支持发推文、关注/取关用户、获取最新消息流。

这道题既考察数据结构的选择，也锻炼系统设计思维。接下来我会用 Swift 详细实现，并提供一个可运行的 Demo 模块，带你一起拆解问题背后的思路。

描述

题目要求设计一个 Twitter 类，具备以下功能：

1. postTweet(userId, tweetId)
   用户 userId 发送一条推文，推文 ID 是 tweetId。

2. getNewsFeed(userId)
   返回用户 userId 的新闻推送，内容包括：

   • 他自己发的推文
   • 他关注的人发的推文
   • 只取最近的 10 条，按时间顺序由新到旧。

3. follow(followerId, followeeId)
   用户 followerId 关注用户 followeeId。

4. unfollow(followerId, followeeId)
   用户 followerId 取关用户 followeeId。

示例

输入：
["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]]

解释：

• 用户 1 发推文 [5]
• 获取新闻流 -> [5]
• 用户 1 关注用户 2
• 用户 2 发推文 [6]
• 用户 1 获取新闻流 -> [6, 5]
• 用户 1 取关用户 2
• 用户 1 获取新闻流 -> [5]

解决答案

设计思路

要满足题目要求，我们需要以下几个关键点：

1. 存储用户发的推文
   使用字典 userTweets: [Int: [(Int, Int)]]，键是 userId，值是推文 (时间戳, tweetId) 列表。

2. 存储用户的关注关系
   使用字典 followees: [Int: Set<Int>]，键是 userId，值是该用户关注的用户集合。

3. 维护时间顺序
   每次发推时记录一个自增的全局时间戳 time，保证推文有先后顺序。

4. 获取新闻流

   • 获取当前用户的推文 + 他关注的人的推文。
   • 合并这些推文，根据时间戳倒序排序，取前 10 条。

虽然这个实现不是最优（可以用堆优化），但对于题目给的约束（最多 3 * 10^4 次操作），完全够用。

题解代码分析

下面是 Swift 的完整实现代码：

import Foundationclass Twitter {private var time = 0private var userTweets: [Int: [(Int, Int)]] = [:]  // userId -> [(time, tweetId)]private var followees: [Int: Set<Int>] = [:]       // userId -> Set of followeesinit() {}// 发推文func postTweet(_ userId: Int, _ tweetId: Int) {time += 1userTweets[userId, default: []].append((time, tweetId))}// 获取新闻流（最近 10 条推文）func getNewsFeed(_ userId: Int) -> [Int] {var tweets: [(Int, Int)] = []// 自己的推文if let selfTweets = userTweets[userId] {tweets.append(contentsOf: selfTweets)}// 关注者的推文if let followeesSet = followees[userId] {for followee in followeesSet {if let followeeTweets = userTweets[followee] {tweets.append(contentsOf: followeeTweets)}}}// 按时间倒序排序，取前 10 条let sortedTweets = tweets.sorted { $0.0 > $1.0 }return sortedTweets.prefix(10).map { $0.1 }}// 关注func follow(_ followerId: Int, _ followeeId: Int) {guard followerId != followeeId else { return }  // 不能关注自己followees[followerId, default: []].insert(followeeId)}// 取关func unfollow(_ followerId: Int, _ followeeId: Int) {followees[followerId]?.remove(followeeId)}
}

测试示例和结果

我们写一个测试函数，模拟题目里的操作：

func testTwitter() {let twitter = Twitter()twitter.postTweet(1, 5)print("News feed of user 1:", twitter.getNewsFeed(1)) // [5]twitter.follow(1, 2)twitter.postTweet(2, 6)print("News feed of user 1 after following 2:", twitter.getNewsFeed(1)) // [6, 5]twitter.unfollow(1, 2)print("News feed of user 1 after unfollowing 2:", twitter.getNewsFeed(1)) // [5]
}testTwitter()

运行结果：

News feed of user 1: [5]
News feed of user 1 after following 2: [6, 5]
News feed of user 1 after unfollowing 2: [5]

时间复杂度

1. postTweet：O(1)
2. follow / unfollow：O(1)
3. getNewsFeed：O(n log n)，其中 n 是自己和关注者的所有推文总数。因为要排序。

在题目约束下（调用次数最多 3 * 10^4），这个解法是可接受的。

空间复杂度

• 存储所有推文：O(totalTweets)
• 存储关注关系：O(totalUsers^2)（最坏情况所有人互相关注）

整体空间复杂度：O(totalTweets + totalFollows)。

总结

这道题考察的不是高深的算法，而是如何合理地组织数据结构：

• 推文需要保存时间顺序，用全局自增计数器解决。
• 用户关系用字典 + 集合管理。
• 获取新闻流时把相关推文合并再排序。

这个设计在真实系统里当然不够高效（Twitter 真实实现用的是复杂的分布式推送系统），但在算法题范围内完全够用。

关键 takeaway：

• 拆分功能：发推、关注、取关、获取新闻流，分别管理。
• 数据结构选型：字典存推文和关系，数组/集合快速操作。
• 排序保证时间顺序：倒序取最近 10 条。