LeetCode 355 Design Twitter

题目链接:Design Twitter

题意:设计一个简单版的Twitter,包括发tweets,关注/取消关注,系统推送自己关注的1o条最新的tweets(包括自己的)

居然随机到了一道设计题,刚开始觉得很简单啊,随便就能实现了,但是仔细想了下,要实现高效率并不简单,中途修改了两次设计,总算是比较满意了。

用一个 HashMap<Integer, HashSet<Integer>> 来记录关注情况,其中 key 为 userId , value 为该用户的 followeeIdSet ,这样可以在 \(O(1)\) 的时间完成查询a是否关注了b和关注/取消关注功能

比较复杂的是推送功能,一开始想的是用一个LinkedHashMap实现tweetId与userId的关联,同时保证tweetId按时间顺序排列,但是这样在推送时最坏需要扫描所有tweetId,这样复杂度就比较高了,因为tweet的数量会比较多。

之后改成了用 HashMap<Integer, ArrayList<Integer>> 来记录每人发的tweets, key 为 userId , value 为该用户的 tweetIdList ,之后在推送时,将该用户所有关注者的 tweetIdList 取出组成一个新的List,之后在每次扫描所有 tweetIdList 的最后一个元素(即最后发布的),找出时间最晚的,放入推送List。这样的复杂度为 \(O(10\times followeeCount)\)\(followeeCount\) 为该用户关注人数

 

 

 

Categories: LeetCode