LeetCode.355.Design Twitter 设计推特

题目描述

355 Design Twitter
https://leetcode-cn.com/problems/design-twitter/

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

1. postTweet(userId, tweetId): Compose a new tweet.
2. getNewsFeed(userId): 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.
3. follow(followerId, followeeId): Follower follows a followee.
4. unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

---

解题过程

使用两个 map 做内部存储结构：
Map<Integer, List<Tweet>> userIdToTweetListMap 存储用户和他的推文列表
Map<Integer, Set<Integer>> userIdToFollowSetMap 存储用户和他的关注列表，由于题中没要求关注列表有序，直接用集合了，方便去重
全局时间戳 timestamp 用于推文按时间排序，每当用户发推时加1

关注、取关、发推的时间复杂度都是 O(1)，拉取推文列表就比较复杂，时间复杂度 O(nlog(n))，其中 n 是每个用户的平均关注数 乘以 每个用户的平均推文数，没做任何优化。
优化：
1、只需保持每个用户的最新 10 条推文，超过 10 条的删除。
2、每个用户的推文列表按时间排序，最新的在链表头部，拉取推文时归并排序，获取到 10 个时就结束
则拉取推文列表的时间复杂度可降低到 O(10n) 其中 n 是每个用户的平均关注数

private static class Twitter {
    // 全局时间戳，每当用户发推时加1
    private int timestamp;
    // 用户 <-> 推文列表 map
    private Map<Integer, List<Tweet>> userIdToTweetListMap;
    // 用户 <-> 关注集合 map
    private Map<Integer, Set<Integer>> userIdToFollowSetMap;

    // 推文类
    class Tweet {
        int id;
        int time;
        Tweet(int id, int time) {
            this.id = id;
            this.time = time;
        }
    }

    public Twitter() {
        timestamp = 1;
        userIdToTweetListMap = new HashMap<>();
        userIdToFollowSetMap = new HashMap<>();
    }

    // 发推
    public void postTweet(int userId, int tweetId) {
        List<Tweet> tweetList = userIdToTweetListMap.computeIfAbsent(userId, k -> new LinkedList<>());
        tweetList.add(new Tweet(tweetId, timestamp++));
    }

    // 拉取用户能看到的最新10条推文
    public List<Integer> getNewsFeed(int userId) {
        // userIdSet 需要查询哪些用户的推文
        Set<Integer> userIdSet = new HashSet<>();
        userIdSet.add(userId);
        userIdSet.addAll(userIdToFollowSetMap.getOrDefault(userId, new HashSet<>()));
        // 查询推文
        List<Tweet> tweetList = new ArrayList<>();
        userIdSet.forEach(uid -> tweetList.addAll(userIdToTweetListMap.getOrDefault(uid, new ArrayList<>())));
        // 按 time 倒序排序
        tweetList.sort((tweet1, tweet2) -> tweet2.time - tweet1.time);
        return tweetList.stream().limit(10).map(tweet -> tweet.id).collect(Collectors.toList());
    }

    // 关注
    public void follow(int followerId, int followeeId) {
        if (followerId == followeeId) {
            // 自己不能关注自己
            return;
        }
        Set<Integer> followSet = userIdToFollowSetMap.computeIfAbsent(followerId, k -> new HashSet<>());
        followSet.add(followeeId);
    }

    // 取关
    public void unfollow(int followerId, int followeeId) {
        Set<Integer> followSet = userIdToFollowSetMap.get(followerId);
        if (null == followSet) {
            return;
        }
        followSet.remove(followeeId);
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_355_DesignTwitter.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_355_DesignTwitter.java

---