LeetCode 355. 设计推特

2021-05-11 HGNULB 约 10 分钟

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

分类

题目描述

✅ 355. 设计推特

题意分析

设计一个简化版推特，支持四个操作：postTweet(userId, tweetId) 发一条推文；getNewsFeed(userId) 返回该用户信息流里最近的至多 10 条推文（包含自己发的和所有关注对象发的），按时间从新到旧排列；follow(followerId, followeeId) 关注；unfollow(followerId, followeeId) 取关。

这是设计题，所以先要把「数据长什么样」和「每个接口的性能契约」定下来。四个操作里三个是 $O(1)$ 量级的写操作，只有 getNewsFeed 是复杂的读操作，全部难点都集中在它身上。

getNewsFeed 的语义拆开看有三层要求：范围是「自己 + 所有关注对象」的推文并集；排序是按发布时间倒序；截断是最多 10 条。三层里最值得利用的是第三层——只要 10 条，就完全不需要把所有推文排一遍序。

「按时间排序」需要一个全局可比较的时间标尺。用户各自的推文列表虽然天然按发布顺序排列，但跨用户之间无法比较先后。所以必须引入一个全局自增的时间戳，每发一条推文就分配一个，数值越大越新。这是本题的第一个必要设计。

还有几处容易被忽略的语义细节：用户可以关注自己（题目样例里不会，但实现要保证不会因此重复统计）；取关一个从未关注过的人应当是无操作而不是报错；给一个从未发过推文、也没关注任何人的用户调 getNewsFeed 应返回空列表而不是抛异常；同一个人被重复 follow 只应算一次。

边界：关注对象的推文可能一条都没有；推文总数可能远超 10 条；关注对象数量可能很大而每人只有一两条推文。

解法：哈希表 + 优先队列

核心思路

每个用户的推文按发布时间追加，天然形成一条从旧到新的有序时间线。获取信息流等价于：合并“自己 + 所有关注者”的多条有序时间线，只取最新 10 条。

给每条推文分配全局递增时间戳。查询时，每个候选用户只把最新推文放入最大堆；弹出全局最新推文后，再把同一用户的前一条推文放入堆。这是截断到 10 条的多路归并，避免把全部历史推文排序。

正确性说明：堆不变量是，每个仍有未输出推文的候选用户恰有一条记录，且是该用户尚未输出的最新推文。因而堆顶就是全局尚未输出的最新推文；弹出后只补入同一时间线的前一项，不变量继续成立。重复至多 10 次，恰好得到按时间倒序的最新 10 条。

关注关系使用集合。查询时再用集合合并本人，可同时避免重复关注和自关注导致同一时间线入堆两次；follow(user,user) 也直接作为无效操作忽略。

终止条件是结果已有 10 条或堆为空。前者满足题目上限，后者说明所有候选时间线都已耗尽。

解题步骤

postTweet 将带全局时间戳的推文追加到用户列表末尾。

follow 向集合加入关注对象，自关注不做任何事；unfollow 从集合删除。

getNewsFeed 建立候选用户集合，包含本人及全部关注对象。

将每个候选用户的最新推文游标加入最大堆。

最多重复 10 次：弹出堆顶加入答案，并将该用户更早一条推文补入堆。

样例中用户 1 发推 5，关注用户 2 后用户 2 发推 6，信息流为 [6,5]；取关后恢复为 [5]。没有推文时堆为空，返回空列表。

如果用户 1 关注自己，候选集合仍只有一个用户 1，其推文不会重复出现。

代码实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

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)
}

复杂度分析

设用户共发布 T 条推文、存在 F 条关注关系，查询用户关注 f 人。

发布、关注、取关： 期望 $O(1)$。

获取信息流： $O((f+10)\log(f+1))$，其中候选时间线为本人加 f 名关注者，堆中至多有 f+1 个游标。

持久空间： $O(T+F)$；单次查询额外使用 $O(f)$ 空间。

关键点总结

每个用户的推文列表本身有序，信息流是“多条有序时间线取前 10”的问题。

全局时间戳提供跨用户可比较的唯一顺序。

堆只保存每条时间线当前最新的未输出项，弹出后再懒加载前一项。

关注关系和查询候选都使用集合，避免重复关注或自关注造成重复推文。

堆空或取满 10 条时结束，结果天然按新到旧排列。

易错点总结

每个用户使用独立时间戳： 无法比较不同用户推文的先后。

把所有历史推文一次性入堆： 查询会退化为与推文总数相关的全量处理。

忘记加入本人： 用户自己的推文不会出现在信息流。

自关注产生第二条本人时间线： 同一推文会重复输出；候选用户必须去重。

弹出后把下标加一： 列表末尾最新，应补入 index-1。

堆比较器用减法： 长时间运行可能溢出，应使用 Long.compare。

相似题目

题目	难度	考察点
23. 合并 K 个升序链表	困难	本题 `getNewsFeed` 的算法原型，同为堆 + 懒加载的 $k$ 路归并，只是不截断
146. LRU 缓存	中等	同为设计题且要求全部接口 $O(1)$，靠哈希表加双向链表，考察结构选型推导
460. LFU 缓存	困难	淘汰依据从时间变成频次加时间，需要按频次分桶，考察多级索引的设计
295. 数据流的中位数	困难	用对顶堆维护动态中位数，重点在两个堆之间的再平衡时机
703. 数据流中的第 K 大元素	简单	固定容量小顶堆的流式维护，是「只要前 K 就不必全排序」的最简载体
380. O(1) 时间插入、删除和获取随机元素	中等	用数组加下标映射满足三个 $O(1)$ 契约，练习为接口契约反推数据结构
707. 设计链表	中等	设计题的基础训练，重点在各接口的下标边界与哨兵节点的使用