设计推特

该题解使用了哈希表和堆来实现一个简化版的推特系统。具体思路如下： 1. 用户与关注者的关系使用哈希表 follow_relation 存储，其中 key 为用户 ID，value 为该用户关注的用户 ID 集合。 2. 用户发布的推文使用哈希表 user_tweets 存储，其中 key 为用户 ID，value 为该用户发布的推文链表的头节点。 3. 发布推文时，创建一个新的推文节点，将其插入到对应用户的推文链表头部。 4. 获取用户的新闻推送时，遍历该用户关注的所有用户（包括自己），将他们的最新推文加入到一个最大堆中，堆的排序依据为推文的时间戳。 5. 从最大堆中依次取出最多 10 条最新的推文 ID，存入结果列表并返回。 6. 关注/取消关注操作通过修改 follow_relation 哈希表实现。

时间复杂度: postTweet: O(1) getNewsFeed: O(NlogM)，其中 N 为关注人数，M 为推文总数 follow: O(1) unfollow: O(1)

空间复杂度: O(F+T)，其中 F 为关注关系总数，T 为推文总数

import time
import heapq
from collections import defaultdict


class Tweet:

    def __init__(self, _id, ts, _next=None):
        self.id = _id
        self.ts = ts
        self.next = _next


class Twitter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.follow_relation = defaultdict(set)  # 用户关注关系哈希表
        self.user_tweets = dict()  # 用户推文哈希表

    def postTweet(self, userId: int, tweetId: int) -> None:
        """
        Compose a new tweet.
        """
        head = self.user_tweets.get(userId)
        if head is None:
            new_head = Tweet(tweetId, time.time_ns())  # 创建新推文节点
        else:
            new_head = Tweet(tweetId, time.time_ns(), _next=head)  # 创建新推文节点并将其插入链表头部
        self.user_tweets[userId] = new_head  # 更新用户推文哈希表

    def getNewsFeed(self, userId: int) -> List[int]:
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        """
        h = []
        for followeeId in self.follow_relation[userId]:  # 遍历关注的用户
            if followeeId in self.user_tweets:
                head = self.user_tweets[followeeId]
                heapq.heappush(h, (-head.ts, head))  # 将关注用户的最新推文加入堆

        if userId in self.user_tweets:  # 将自己的最新推文也加入堆
            head = self.user_tweets[userId]
            heapq.heappush(h, (-head.ts, head))

        ret = []
        while h:
            _, tweet = heapq.heappop(h)  # 从堆中取出时间戳最大的推文
            ret.append(tweet.id)
            if len(ret) == 10:  # 最多返回 10 条推文
                return ret
            if tweet.next:  # 将下一条推文加入堆
                heapq.heappush(h, (-tweet.next.ts, tweet.next))
        return ret

    def follow(self, followerId: int, followeeId: int) -> None:
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        """
        if followeeId == followerId:
            return

        self.follow_relation[followerId].add(followeeId)  # 更新关注关系哈希表

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        """
        self.follow_relation[followerId].discard(followeeId)  # 更新关注关系哈希表


# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)