门户网站功能清单,wordpress 站点描述,微信下拉小程序怎么关闭,变装小说wordpress文章目录摘要描述示例解决答案设计思路题解代码分析测试示例和结果时间复杂度空间复杂度总结摘要
在社交媒体平台里#xff0c;推送机制是核心功能之一。比如你关注了某人#xff0c;就希望在自己的时间线上能看到他们的最新消息#xff0c;同时自己的消息也要能出现在别人… 文章目录摘要描述示例解决答案设计思路题解代码分析测试示例和结果时间复杂度空间复杂度总结摘要
在社交媒体平台里推送机制是核心功能之一。比如你关注了某人就希望在自己的时间线上能看到他们的最新消息同时自己的消息也要能出现在别人的首页。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: SetInt]键是 userId值是该用户关注的用户集合。 维护时间顺序 每次发推时记录一个自增的全局时间戳 time保证推文有先后顺序。 获取新闻流 获取当前用户的推文 他关注的人的推文。合并这些推文根据时间戳倒序排序取前 10 条。
虽然这个实现不是最优可以用堆优化但对于题目给的约束最多 3 * 10^4 次操作完全够用。 题解代码分析
下面是 Swift 的完整实现代码
import Foundationclass Twitter {private var time 0private var userTweets: [Int: [(Int, Int)]] [:] // userId - [(time, tweetId)]private var followees: [Int: SetInt] [:] // 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]时间复杂度
postTweetO(1)follow / unfollowO(1)getNewsFeedO(n log n)其中 n 是自己和关注者的所有推文总数。因为要排序。
在题目约束下调用次数最多 3 * 10^4这个解法是可接受的。
空间复杂度
存储所有推文O(totalTweets)存储关注关系O(totalUsers^2)最坏情况所有人互相关注
整体空间复杂度O(totalTweets totalFollows)。
总结
这道题考察的不是高深的算法而是如何合理地组织数据结构
推文需要保存时间顺序用全局自增计数器解决。用户关系用字典 集合管理。获取新闻流时把相关推文合并再排序。
这个设计在真实系统里当然不够高效Twitter 真实实现用的是复杂的分布式推送系统但在算法题范围内完全够用。
关键 takeaway
拆分功能发推、关注、取关、获取新闻流分别管理。数据结构选型字典存推文和关系数组/集合快速操作。排序保证时间顺序倒序取最近 10 条。
