355. Design Twitter

題目網址：https://leetcode.cn/problems/design-twitter/

題意：設計一個簡化版的 Twitter, 可以讓用戶實現發送推文、關注 / 取消關注其他用戶, 以及能夠看見關注人（包括自己）的最近 10 條推文。

Twitter()：初始化 twitter instance。

void postTweet(int userId, int tweetId)：根據給定的 tweetId 和 userId 創建一條新推文。每次調用此函數都會使用一個不同的 tweetId。

List<Integer> getNewsFeed(int userId)：檢索當前用戶新聞推送中最近 10 條推文的 ID。

新聞推送中的每一項都必須是由用戶關注的人 or 用戶自己發布的推文。

推文必須按照時間順序由最近到最遠排序。

void follow(int followerId, int followeeId)：ID 為 followerId 的用戶開始關注 ID 為 followeeId 的用戶。

void unfollow(int followerId, int followeeId)：ID 為 followerId 的用戶取消關注 ID 為 followeeId 的用戶。

Solution 1：

想法：利用 hash table, 利用兩個 hash table friends、tweets 來分別記錄每一位用戶的好友、每一位用戶發的推文。getNewsFeed() 獲取自己和好友的最近 10 條推文, 首先要將自己添增到自己的好友列表中, 然後依序遍歷每個好友的所有推文, 並維護一個大小為 10 的 min heap

typedef pair<int, int> pii;

class Twitter {
public:
    Twitter() {
        ts = 0;
    }

    void postTweet(int userId, int tweetId) {
        tweets[userId].emplace_back(pii{++ts, tweetId});
    }

    vector<int> getNewsFeed(int userId) {
        follow(userId, userId); // 先 follow 自己

        priority_queue<pii, vector<pii>, greater<>> pq; // min heap
        for (const auto i : friends[userId]) {
            // 遍歷該好友「最新 -> 最舊」的推文
            for (int j = tweets[i].size() - 1; j >= 0; --j) {
                pq.emplace(tweets[i][j]);
                if (pq.size() > 10) { // 若大於 10 則, 則 pop 掉 ts 最小的, 以維持 10 則
                    pq.pop();
                }
            }
        }

        // 取出 的 tweetId 是根據 ts 由小到大排序, 故取出後要 reverse
        vector<int> res;
        while (!pq.empty()) {
            res.emplace_back(pq.top().second);
            pq.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }

    void follow(int followerId, int followeeId) {
        friends[followerId].emplace(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        if (friends[followerId].find(followeeId) != friends[followerId].end()) {
            friends[followerId].erase(followeeId);
        }
    }

private:
    int ts; // timestamp, ts 越大代表該推文越新
    unordered_map<int, vector<pii>> tweets; // userId -> {ts, tweetId}
    unordered_map<int, unordered_set<int>> friends; // {follower, set of followee}
};

time：
- Twitter()：$O(1)$
- postTweet()：$O(1)$
- getNewsFeed()：$O(f \cdot t)$ ➔ $O(f \cdot t \cdot log(10))$, 遍歷該用戶每個好友的所有推文
  - f 為該用戶的好友數
  - t 為每位好友的平均推文數
  - $O(log(10))$ 為 heap 中 insert / erase 一個元素所需的時間
- follow()：$O(1)$
- unfollow()：$O(1)$
space：$O(u \cdot t)$ ➔ tweets, 其中 u 為所有用戶數, t 為所有用戶的平均推文數

Solution 2：

想法：同 Solution 1, 只是 getNewsFeed() 改成維護一個大小為 10 的 set, 並做 pruning 來優化。每個好友的推文是根據 ts 「大(新) -> 小(舊)」來遍歷, 一旦當前好友 f1 的推文比 news 中最舊推文的 ts 還要小, 則 f1 剩餘的推文都不必遍歷（因為 ts 只會更小）, 可直接跳到下一個好友

typedef pair<int, int> pii;

class Twitter {
public:
    Twitter() {
        ts = 0;
    }

    void postTweet(int userId, int tweetId) {
        tweets[userId].emplace_back(pii{++ts, tweetId});
    }

    vector<int> getNewsFeed(int userId) {
        follow(userId, userId); // 先 follow 自己

        set<pii> news;
        for (const auto i : friends[userId]) {
            // 遍歷該好友「最新 -> 最舊」的推文
            for (int j = tweets[i].size() - 1; j >= 0; --j) {
                // 不足 10 則, 直接加入到 news 中
                if (news.size() < 10) {
                    news.emplace(tweets[i][j]);
                } else if (tweets[i][j].first > news.begin()->first) { // 若該推文比 news 中最舊的推文還新, 則加入該推文, 並移除最舊的推文
                    news.erase(news.begin());
                    news.emplace(tweets[i][j]);
                } else { // 該推文比 news 中最舊的推文還舊, 則該好友不必再繼續往下遍歷
                    break;
                }
            }
        }

        // 取出 news 中的 tweetId, 由於 news 是根據 ts 由小到大排序, 故取出後要 reverse
        vector<int> res;
        for (const auto& [ts, tweetId] : news) {
            res.emplace_back(tweetId);
        }
        reverse(res.begin(), res.end());
        return res;
    }

    void follow(int followerId, int followeeId) {
        friends[followerId].emplace(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        if (friends[followerId].find(followeeId) != friends[followeeId].end()) {
            friends[followerId].erase(followeeId);
        }
    }

private:
    int ts; // timestamp, ts 越大代表該推文越新
    unordered_map<int, vector<pii>> tweets; // userId -> {ts, tweetId}
    unordered_map<int, unordered_set<int>> friends; // {follower, set of followee}
};

time：
- Twitter()：$O(1)$
- postTweet()：$O(1)$
- getNewsFeed()：$O(f \cdot t)$ ➔ $O(f \cdot t \cdot log(10))$, 遍歷該用戶每個好友的所有推文
  - f 為該用戶的好友數
  - t 為每位好友的平均推文數
  - $O(log(10))$ 為 set 中 insert / erase 一個元素所需的時間
- follow() : $O(1)$
- unfollow() : $O(1)$
space：$O(u \cdot t)$ ➔ tweets, 其中 u 為所有用戶數, t 為所有用戶的平均推文數