LeetCode 355. 设计推特

2021-05-11 HGNULB 约 8 分钟

文章信息 6 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 1-2 字节

题目描述

✅ 355. 设计推特

题意分析

支持发布推文、关注、取消关注和查询信息流。一次查询要从“本人及当前关注对象”的所有推文中取出最新的至多十条，按发布时间从新到旧返回编号。

推文编号只标识推文，不代表发布时间。关注关系的变化影响下一次查询的来源，不应删除任何用户已经发布的历史推文；查询本身也不能把推文消费掉。

解法：多路归并 + 最大堆

核心思路

[!blue]

分别保存两类状态：tweets[user] 是用户按发布顺序追加的推文列表，follows[user] 是该用户关注对象的集合。每次发布都使用同一个全局递增时间戳，因此不同用户的推文也能比较先后；列表末尾就是该用户最新的一条。

查询时，需要把多条“从末尾向前读取”的有序时间线合并，但只取前十项。先把关注对象复制到本次查询的来源集合，再加入本人，确保自己的推文始终可见。集合还能保证同一来源不会重复入堆；没有发布过推文的用户直接略过。

对每条非空时间线，只把最新一条放入按时间戳排序的最大堆。堆中元素是一个游标，记录所属用户、列表下标和当前推文，这样取出后才知道从哪里继续读取。

为什么堆顶就是全局下一条？每条时间线尚未输出的推文中，最新的一条已经在堆里，该用户更早的推文都不会比它更新。因此所有来源的最新候选中时间戳最大的那个，也是全部尚未输出推文中最新的那个，可以直接加入答案。

弹出一个游标后，只需把同一用户的前一条推文补入堆：它成为这条时间线新的最新候选，其他来源的候选保持不变。这样每轮都恢复“每条未耗尽时间线恰有一个最新候选”的不变量，连续弹出便得到从新到旧的全局顺序。

输出达到十条时停止，堆提前为空则说明可见推文不足十条。游标与堆都是本次查询的临时状态，不修改历史列表，所以重复查询仍能返回同样的可见消息。关注、取关只增删集合成员，下一次查询重新收集来源即可反映变化。

解题步骤

发布时追加推文编号和全局时间戳。

关注、取关分别维护关注对象集合。

查询时将本人和关注对象的最新推文游标入堆。

最多弹出十条，每次补入对应时间线的前一条，堆空则结束。

代码实现

class Twitter {
    private static class Tweet {
        final int id;
        final long time;

        Tweet(int id, long time) {
            this.id = id;
            this.time = time;
        }
    }

    private static class Cursor {
        final int userId;
        final int index;
        final Tweet tweet;

        Cursor(int userId, int index, Tweet tweet) {
            this.userId = userId;
            this.index = index;
            this.tweet = tweet;
        }
    }

    private long timestamp;
    private final Map<Integer, List<Tweet>> tweets = new HashMap<>();
    private final Map<Integer, Set<Integer>> follows = new HashMap<>();

    public Twitter() {}

    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, key -> new ArrayList<>())
                .add(new Tweet(tweetId, timestamp++));
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> users = new HashSet<>(follows.getOrDefault(userId, Collections.emptySet()));

        // 候选来源包括本人及关注对象，同一时间线只加入一次。
        users.add(userId);

        // 每条候选时间线只放入当前最新的未输出推文。
        PriorityQueue<Cursor> heap =
                new PriorityQueue<>((a, b) -> Long.compare(b.tweet.time, a.tweet.time));

        for (int user : users) {
            List<Tweet> timeline = tweets.get(user);

            if (timeline != null && !timeline.isEmpty()) {
                int index = timeline.size() - 1;

                heap.offer(new Cursor(user, index, timeline.get(index)));
            }
        }

        List<Integer> answer = new ArrayList<>(10);

        while (!heap.isEmpty() && answer.size() < 10) {
            Cursor current = heap.poll();

            answer.add(current.tweet.id);

            // 列表末尾最新，弹出后只补同一用户更早的一条。
            int previous = current.index - 1;

            if (previous >= 0) {
                List<Tweet> timeline = tweets.get(current.userId);

                heap.offer(new Cursor(current.userId, previous, timeline.get(previous)));
            }
        }

        return answer;
    }

    public void follow(int followerId, int followeeId) {
        if (followerId != followeeId) {
            follows.computeIfAbsent(followerId, key -> new HashSet<>()).add(followeeId);
        }
    }

    public void unfollow(int followerId, int followeeId) {
        Set<Integer> following = follows.get(followerId);

        if (following != null) {
            following.remove(followeeId);
        }
    }
}

import "container/heap"

type tweet struct {
    id   int
    time int64
}

type feedCursor struct {
    userID int
    index  int
    tweet  tweet
}

type feedHeap []feedCursor

func (h feedHeap) Len() int { return len(h) }

func (h feedHeap) Less(i, j int) bool { return h[i].tweet.time > h[j].tweet.time }

func (h feedHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *feedHeap) Push(value any) { *h = append(*h, value.(feedCursor)) }

func (h *feedHeap) Pop() any {
    old := *h
    last := len(old) - 1
    value := old[last]
    *h = old[:last]
    return value
}

type Twitter struct {
    timestamp int64
    tweets    map[int][]tweet
    follows   map[int]map[int]struct{}
}

func Constructor() Twitter {
    return Twitter{
        tweets:  make(map[int][]tweet),
        follows: make(map[int]map[int]struct{}),
    }
}

func (t *Twitter) PostTweet(userID int, tweetID int) {
    t.tweets[userID] = append(
        t.tweets[userID], tweet{id: tweetID, time: t.timestamp})
    t.timestamp++
}

func (t *Twitter) GetNewsFeed(userID int) []int {
    // 候选来源包括本人及关注对象，同一时间线只加入一次。
    users := map[int]struct{}{userID: {}}
    for followeeID := range t.follows[userID] {
        users[followeeID] = struct{}{}
    }

    // 每条候选时间线只放入当前最新的未输出推文。
    queue := &feedHeap{}
    for user := range users {
        timeline := t.tweets[user]
        if len(timeline) > 0 {
            index := len(timeline) - 1
            heap.Push(queue, feedCursor{
                userID: user,
                index:  index,
                tweet:  timeline[index],
            })
        }
    }

    answer := make([]int, 0, 10)
    for queue.Len() > 0 && len(answer) < 10 {
        current := heap.Pop(queue).(feedCursor)
        answer = append(answer, current.tweet.id)

        // 列表末尾最新，弹出后只补同一用户更早的一条。
        previous := current.index - 1
        if previous >= 0 {
            timeline := t.tweets[current.userID]
            heap.Push(queue, feedCursor{
                userID: current.userID,
                index:  previous,
                tweet:  timeline[previous],
            })
        }
    }
    return answer
}

func (t *Twitter) Follow(followerID int, followeeID int) {
    if followerID == followeeID {
        return
    }
    if t.follows[followerID] == nil {
        t.follows[followerID] = make(map[int]struct{})
    }
    t.follows[followerID][followeeID] = struct{}{}
}

func (t *Twitter) Unfollow(followerID int, followeeID int) {
    delete(t.follows[followerID], followeeID)
}

复杂度分析

时间复杂度：发布期望摊还 $O(1)$，关注和取关期望 $O(1)$；设关注集合的遍历规模为 f，查询为 $O((f+11)\log(f+2))$，包含候选收集与逐条入堆。

空间复杂度：持久存储 $O(U+T+F)$，U 为保留用户条目规模，T 为推文存储规模，F 为关注集合存储规模；集合容量不会因每次取关立即缩减。单次查询额外 $O(f+1)$。

关键点总结

[!green]

候选来源是关注对象，不是关注自己的人。

全局时间戳确定跨用户先后，推文编号不代表时间。

每条时间线只保留一个待输出游标。

易错点总结

[!yellow]

忘记加入本人：自己的推文被漏掉。

每次将全部历史推文入堆：查询成本随历史总量增长。

弹出后补 index+1：列表末尾最新，应向前取旧推文。

按各用户独立时间排序：无法判断不同用户间的发布时间先后。

相似题目

题目	难度	关联与区别
23. 合并 K 个升序链表	困难	每个用户的推文流按时间有序，合并多个关注者的最新消息可复用多路归并。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/62239190

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！