摘要

在社交媒體平臺里，推送機制是核心功能之一。比如你關注了某人，就希望在自己的時間線上能看到他們的最新消息，同時自己的消息也要能出現在別人的首頁。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 條。