读完本文，你能够去力扣拿下如下题目：
355.设计推特
-----------
「design Twitter」是 LeetCode 上第 355 道题目，不仅题目自身很有意思，而且把合并多个有序链表的算法和面向对象设计（OO design）联合起来了，很有实际意义，本文就带大家来看看这道题。
至于 Twitter 的什么性能跟算法有关系，等咱们形容一下题目要求就晓得了。
一、题目及利用场景简介
Twitter 和微博性能差不多，咱们次要要实现这样几个 API：
class Twitter { /** user 发表一条 tweet 动静 */ public void postTweet(int userId, int tweetId) {} /** 返回该 user 关注的人（包含他本人）最近的动静 id， 最多 10 条，而且这些动静必须按从新到旧的工夫线顺序排列。*/ public List<Integer> getNewsFeed(int userId) {} /** follower 关注 followee，如果 Id 不存在则新建 */ public void follow(int followerId, int followeeId) {} /** follower 取关 followee，如果 Id 不存在则什么都不做 */ public void unfollow(int followerId, int followeeId) {}}举个具体的例子，不便大家了解 API 的具体用法：
Twitter twitter = new Twitter();twitter.postTweet(1, 5);// 用户 1 发送了一条新推文 5twitter.getNewsFeed(1);// return [5]，因为本人是关注本人的twitter.follow(1, 2);// 用户 1 关注了用户 2twitter.postTweet(2, 6);// 用户2发送了一个新推文 (id = 6)twitter.getNewsFeed(1);// return [6, 5]// 解释：用户 1 关注了本人和用户 2，所以返回他们的最近推文// 而且 6 必须在 5 之前，因为 6 是最近发送的twitter.unfollow(1, 2);// 用户 1 勾销关注了用户 2twitter.getNewsFeed(1);// return [5]这个场景在咱们的现实生活中十分常见。拿朋友圈举例，比方我刚加到女神的微信，而后我去刷新一下我的朋友圈动静，那么女神的动静就会呈现在我的动静列表，而且会和其余动静按工夫排好序。只不过 Twitter 是单向关注，微信好友相当于双向关注。除非，被屏蔽...
这几个 API 中大部分都很好实现，最外围的性能难点应该是 getNewsFeed，因为返回的后果必须在工夫上有序，但问题是用户的关注是动态变化的，怎么办？
这里就波及到算法了：如果咱们把每个用户各自的推文存储在链表里，每个链表节点存储文章 id 和一个工夫戳 time（记录发帖工夫以便比拟），而且这个链表是按 time 有序的，那么如果某个用户关注了 k 个用户，咱们就能够用合并 k 个有序链表的算法合并出有序的推文列表，正确地 getNewsFeed 了！
具体的算法等会解说。不过，就算咱们把握了算法，应该如何编程示意用户 user 和推文动静 tweet 能力把算法流畅地用进去呢？这就波及简略的面向对象设计了，上面咱们来由浅入深，一步一步进行设计。
二、面向对象设计
依据方才的剖析，咱们须要一个 User 类，贮存 user 信息，还须要一个 Tweet 类，贮存推文信息，并且要作为链表的节点。所以咱们先搭建一下整体的框架：
class Twitter { private static int timestamp = 0; private static class Tweet {} private static class User {} /* 还有那几个 API 办法 */ public void postTweet(int userId, int tweetId) {} public List<Integer> getNewsFeed(int userId) {} public void follow(int followerId, int followeeId) {} public void unfollow(int followerId, int followeeId) {}}之所以要把 Tweet 和 User 类放到 Twitter 类外面，是因为 Tweet 类必须要用到一个全局工夫戳 timestamp，而 User 类又须要用到 Tweet 类记录用户发送的推文，所以它们都作为外部类。不过为了清晰和简洁，下文会把每个外部类和 API 办法独自拿进去实现。
1、Tweet 类的实现
依据后面的剖析，Tweet 类很容易实现：每个 Tweet 实例须要记录本人的 tweetId 和发表工夫 time，而且作为链表节点，要有一个指向下一个节点的 next 指针。
class Tweet { private int id; private int time; private Tweet next; // 须要传入推文内容（id）和发文工夫 public Tweet(int id, int time) { this.id = id; this.time = time; this.next = null; }}2、User 类的实现
咱们依据理论场景想一想，一个用户须要存储的信息有 userId，关注列表，以及该用户发过的推文列表。其中关注列表应该用汇合（Hash Set）这种数据结构来存，因为不能反复，而且须要疾速查找；推文列表应该由链表这种数据结构贮存，以便于进行有序合并的操作。画个图了解一下：
除此之外，依据面向对象的设计准则，「关注」「取关」和「发文」应该是 User 的行为，况且关注列表和推文列表也存储在 User 类中，所以咱们也应该给 User 增加 follow，unfollow 和 post 这几个办法：
// static int timestamp = 0class User { private int id; public Set<Integer> followed; // 用户发表的推文链表头结点 public Tweet head; public User(int userId) { followed = new HashSet<>(); this.id = userId; this.head = null; // 关注一下本人 follow(id); } public void follow(int userId) { followed.add(userId); } public void unfollow(int userId) { // 不能够取关本人 if (userId != this.id) followed.remove(userId); } public void post(int tweetId) { Tweet twt = new Tweet(tweetId, timestamp); timestamp++; // 将新建的推文插入链表头 // 越靠前的推文 time 值越大 twt.next = head; head = twt; }}3、几个 API 办法的实现
class Twitter { private static int timestamp = 0; private static class Tweet {...} private static class User {...} // 咱们须要一个映射将 userId 和 User 对象对应起来 private HashMap<Integer, User> userMap = new HashMap<>(); /** user 发表一条 tweet 动静 */ public void postTweet(int userId, int tweetId) { // 若 userId 不存在，则新建 if (!userMap.containsKey(userId)) userMap.put(userId, new User(userId)); User u = userMap.get(userId); u.post(tweetId); } /** follower 关注 followee */ public void follow(int followerId, int followeeId) { // 若 follower 不存在，则新建 if(!userMap.containsKey(followerId)){ User u = new User(followerId); userMap.put(followerId, u); } // 若 followee 不存在，则新建 if(!userMap.containsKey(followeeId)){ User u = new User(followeeId); userMap.put(followeeId, u); } userMap.get(followerId).follow(followeeId); } /** follower 取关 followee，如果 Id 不存在则什么都不做 */ public void unfollow(int followerId, int followeeId) { if (userMap.containsKey(followerId)) { User flwer = userMap.get(followerId); flwer.unfollow(followeeId); } } /** 返回该 user 关注的人（包含他本人）最近的动静 id， 最多 10 条，而且这些动静必须按从新到旧的工夫线顺序排列。*/ public List<Integer> getNewsFeed(int userId) { // 须要了解算法，见下文 }}三、算法设计
实现合并 k 个有序链表的算法须要用到优先级队列（Priority Queue），这种数据结构是「二叉堆」最重要的利用，你能够了解为它能够对插入的元素主动排序。乱序的元素插入其中就被放到了正确的地位，能够依照从小到大（或从大到小）有序地取出元素。
PriorityQueue pq# 乱序插入for i in {2,4,1,9,6}: pq.add(i)while pq not empty: # 每次取出第一个（最小）元素 print(pq.pop())# 输入有序：1,2,4,6,9借助这种牛逼的数据结构反对，咱们就很容易实现这个外围性能了。留神咱们把优先级队列设为按 time 属性从大到小降序排列，因为 time 越大意味着工夫越近，应该排在后面：
public List<Integer> getNewsFeed(int userId) { List<Integer> res = new ArrayList<>(); if (!userMap.containsKey(userId)) return res; // 关注列表的用户 Id Set<Integer> users = userMap.get(userId).followed; // 主动通过 time 属性从大到小排序，容量为 users 的大小 PriorityQueue<Tweet> pq = new PriorityQueue<>(users.size(), (a, b)->(b.time - a.time)); // 先将所有链表头节点插入优先级队列 for (int id : users) { Tweet twt = userMap.get(id).head; if (twt == null) continue; pq.add(twt); } while (!pq.isEmpty()) { // 最多返回 10 条就够了 if (res.size() == 10) break; // 弹出 time 值最大的（最近发表的） Tweet twt = pq.poll(); res.add(twt.id); // 将下一篇 Tweet 插入进行排序 if (twt.next != null) pq.add(twt.next); } return res;}这个过程是这样的，上面是我制作的一个 GIF 图形容合并链表的过程。假如有三个 Tweet 链表按 time 属性降序排列，咱们把他们降序合并增加到 res 中。留神图中链表节点中的数字是 time 属性，不是 id 属性：
至此，这道一个极其简化的 Twitter 工夫线性能就设计结束了。
四、最初总结
本文使用简略的面向对象技巧和合并 k 个有序链表的算法设计了一套简化的工夫线性能，这个性能其实宽泛地使用在许多社交利用中。
咱们先正当地设计出 User 和 Tweet 两个类，而后基于这个设计之上使用算法解决了最重要的一个性能。可见理论利用中的算法并不是孤立存在的，须要和其余常识混合使用，能力施展理论价值。
当然，理论利用中的社交 App 数据量是微小的，思考到数据库的读写性能，咱们的设计可能承受不住流量压力，还是有些太简化了。而且理论的利用都是一个极其宏大的工程，比方下图，是 Twitter 这样的社交网站大抵的系统结构：
咱们解决的问题应该只能算 Timeline Service 模块的一小部分，性能越多，零碎的复杂性可能是指数级增长的。所以说正当的顶层设计非常重要，其作用是远超某一个算法的。
最初，Github 上有一个优良的开源我的项目，专门收集了很多大型零碎设计的案例和解析，而且有中文版本，下面这个图也出自该我的项目。对系统设计感兴趣的读者能够点击 这里 查看。
PS：本文前两张图片和 GIF 是我第一次尝试用平板的绘图软件制作的，花了很多工夫，尤其是 GIF 图，须要一帧一帧制作。如果本文内容对你有帮忙，点个赞分个享，激励一下我呗！