摘要
在社交媒体平台里，推送机制是核心功能之一。比如你关注了某人，就希望在自己的时间线上能看到他们的最新消息，同时自己的消息也要能出现在别人的首页。LeetCode 355 题——“设计推特”就把这个场景简化成一个核心设计题。我们要实现一个小型 Twitter 系统，支持发推文、关注/取关用户、获取最新消息流。
这道题既考察数据结构的选择，也锻炼系统设计思维。接下来我会用 Swift 详细实现，并提供一个可运行的 Demo 模块，带你一起拆解问题背后的思路。
描述
题目要求设计一个 Twitter 类，具备以下功能：
postTweet(userId, tweetId)
用户userId发送一条推文，推文 ID 是tweetId。getNewsFeed(userId)
返回用户userId的新闻推送，内容包括：- 他自己发的推文
- 他关注的人发的推文
- 只取最近的 10 条，按时间顺序由新到旧。
follow(followerId, followeeId)
用户followerId关注用户followeeId。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]
解决答案
设计思路
要满足题目要求，我们需要以下几个关键点：
存储用户发的推文
使用字典userTweets: [Int: [(Int, Int)]]，键是userId，值是推文(时间戳, tweetId)列表。存储用户的关注关系
使用字典followees: [Int: Set<Int>]，键是userId，值是该用户关注的用户集合。维护时间顺序
每次发推时记录一个自增的全局时间戳time，保证推文有先后顺序。获取新闻流
- 获取当前用户的推文 + 他关注的人的推文。
- 合并这些推文，根据时间戳倒序排序，取前 10 条。
虽然这个实现不是最优（可以用堆优化），但对于题目给的约束（最多 3 * 10^4 次操作），完全够用。
题解代码分析
下面是 Swift 的完整实现代码：
import Foundation
class Twitter {
private var time = 0
private var userTweets: [Int: [(Int, Int)]] = [:] // userId -> [(time, tweetId)]
private var followees: [Int: Set<Int>] = [:] // userId -> Set of followees
init() {}
// 发推文
func postTweet(_ userId: Int, _ tweetId: Int) {
time += 1
userTweets[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]
时间复杂度
- postTweet：O(1)
- follow / unfollow：O(1)
- getNewsFeed：O(n log n)，其中 n 是自己和关注者的所有推文总数。因为要排序。
在题目约束下（调用次数最多 3 * 10^4），这个解法是可接受的。
空间复杂度
- 存储所有推文：O(totalTweets)
- 存储关注关系：O(totalUsers^2)（最坏情况所有人互相关注）
整体空间复杂度：O(totalTweets + totalFollows)。
总结
这道题考察的不是高深的算法，而是如何合理地组织数据结构：
- 推文需要保存时间顺序，用全局自增计数器解决。
- 用户关系用字典 + 集合管理。
- 获取新闻流时把相关推文合并再排序。
这个设计在真实系统里当然不够高效（Twitter 真实实现用的是复杂的分布式推送系统），但在算法题范围内完全够用。
关键 takeaway：
- 拆分功能：发推、关注、取关、获取新闻流，分别管理。
- 数据结构选型：字典存推文和关系，数组/集合快速操作。
- 排序保证时间顺序：倒序取最近 10 条。