讀完本文，你可以去力扣拿下如下題目：
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 模組的一小部分，功能越多，系統的複雜性可能是指數級增長的。所以說合理的頂層設計十分重要，其作用是遠超某一個演算法的。