355. 设计推特

中等设计哈希表 + 收集候选后排序力扣原题 ↗

题目描述

设计一个简化的推特类 Twitter，支持发推、关注、取消关注，以及查看动态。

Twitter()：创建空的系统。postTweet(userId, tweetId)：用户 userId 发出一条编号为 tweetId 的推文，无返回值。每次调用的 tweetId 都不同。

getNewsFeed(userId)：返回该用户动态里最新的至多 10 条推文编号。动态只包含用户自己发的推文和他当前关注的人发的推文。结果按发布时间从新到旧排列。

follow(followerId, followeeId)：followerId 开始关注 followeeId。unfollow(followerId, followeeId)：followerId 不再关注 followeeId。这两个方法都无返回值。

示例按操作序列给出：第一行是方法名，第二行是参数，输出中无返回值的调用记为 null。

示例 1

输入：操作 = ["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"]
参数 = [[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]
输出：[null,null,[5],null,null,[6,5],null,[5]]

解释：用户 1 关注用户 2 后能看到推文 6 和 5，6 更新所以在前；取消关注后只剩自己的推文 5。

数据范围

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 10^4
所有推文编号互不相同。
四个方法合计最多调用 3 * 10^4 次。
用户不会关注自己。

解题思路：哈希表 + 收集候选后排序

全局时间戳 time 每发一条推文自增；每个用户保存 (time, tweetId) 列表和关注集合。拉 feed 时，把自己和每个关注者的最新 10 条放进候选，按时间降序取前 10 条。也可用堆做 k 路归并进一步优化。

为什么正确

每个用户的推文列表按时间戳升序，末尾最新；关注集合里没有自己。

复杂度分析

post / follow / unfollow O(1)；feed O(F·10·log(F·10))，F 为关注人数。

易错点

关注自己时要忽略，否则自己的推文可能被加入两次；排序依据是时间戳而非 tweetId。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)
        self.follows = defaultdict(set)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.time += 1
        self.tweets[userId].append((self.time, tweetId))

    def getNewsFeed(self, userId: int) -> List[int]:
        cand = []
        for u in self.follows[userId] | {userId}:
            cand.extend(self.tweets[u][-10:])
        cand.sort(reverse=True)
        return [tid for _, tid in cand[:10]]

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.follows[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].discard(followeeId)

class Twitter {
    private int time = 0;
    private final Map<Integer, List<int[]>> tweets = new HashMap<>();
    private final Map<Integer, Set<Integer>> follows = new HashMap<>();

    public Twitter() {
    }

    public void postTweet(int userId, int tweetId) {
        time++;
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{time, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        List<int[]> cand = new ArrayList<>();
        Set<Integer> users = new HashSet<>(follows.getOrDefault(userId, new HashSet<>()));
        users.add(userId);
        for (int u : users) {
            List<int[]> t = tweets.getOrDefault(u, new ArrayList<>());
            cand.addAll(t.subList(Math.max(0, t.size() - 10), t.size()));
        }
        cand.sort((x, y) -> y[0] - x[0]);
        List<Integer> res = new ArrayList<>();
        for (int k = 0; k < cand.size() && k < 10; k++)
            res.add(cand.get(k)[1]);
        return res;
    }

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

    public void unfollow(int followerId, int followeeId) {
        follows.getOrDefault(followerId, new HashSet<>()).remove(followeeId);
    }
}

class Twitter {
    int time = 0;
    unordered_map<int, vector<pair<int, int>>> tweets;
    unordered_map<int, unordered_set<int>> follows;
public:
    Twitter() {}

    void postTweet(int userId, int tweetId) {
        time++;
        tweets[userId].push_back({time, tweetId});
    }

    vector<int> getNewsFeed(int userId) {
        vector<pair<int, int>> cand;
        unordered_set<int> users = follows[userId];
        users.insert(userId);
        for (int u : users) {
            auto& t = tweets[u];
            for (int k = max(0, (int)t.size() - 10); k < (int)t.size(); k++)
                cand.push_back(t[k]);
        }
        sort(cand.rbegin(), cand.rend());
        vector<int> res;
        for (int k = 0; k < (int)cand.size() && k < 10; k++)
            res.push_back(cand[k].second);
        return res;
    }

    void follow(int followerId, int followeeId) {
        if (followerId != followeeId)
            follows[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        follows[followerId].erase(followeeId);
    }
};

type Twitter struct {
	time    int
	tweets  map[int][][2]int
	follows map[int]map[int]bool
}

func Constructor() Twitter {
	return Twitter{0, map[int][][2]int{}, map[int]map[int]bool{}}
}

func (this *Twitter) PostTweet(userId int, tweetId int) {
	this.time++
	this.tweets[userId] = append(this.tweets[userId], [2]int{this.time, tweetId})
}

func (this *Twitter) GetNewsFeed(userId int) []int {
	cand := [][2]int{}
	users := []int{userId}
	for u := range this.follows[userId] {
		users = append(users, u)
	}
	for _, u := range users {
		t := this.tweets[u]
		cand = append(cand, t[max(0, len(t)-10):]...)
	}
	sort.Slice(cand, func(a, b int) bool { return cand[a][0] > cand[b][0] })
	res := []int{}
	for k := 0; k < len(cand) && k < 10; k++ {
		res = append(res, cand[k][1])
	}
	return res
}

func (this *Twitter) Follow(followerId int, followeeId int) {
	if followerId != followeeId {
		if this.follows[followerId] == nil {
			this.follows[followerId] = map[int]bool{}
		}
		this.follows[followerId][followeeId] = true
	}
}

func (this *Twitter) Unfollow(followerId int, followeeId int) {
	delete(this.follows[followerId], followeeId)
}

var Twitter = function() {
    this.time = 0;
    this.tweets = new Map();
    this.follows = new Map();
};

Twitter.prototype.postTweet = function(userId, tweetId) {
    this.time++;
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId).push([this.time, tweetId]);
};

Twitter.prototype.getNewsFeed = function(userId) {
    const cand = [];
    const users = new Set(this.follows.get(userId) || []);
    users.add(userId);
    for (const u of users)
        cand.push(...(this.tweets.get(u) || []).slice(-10));
    cand.sort((a, b) => b[0] - a[0]);
    return cand.slice(0, 10).map(x => x[1]);
};

Twitter.prototype.follow = function(followerId, followeeId) {
    if (followerId === followeeId)
        return;
    if (!this.follows.has(followerId)) this.follows.set(followerId, new Set());
    this.follows.get(followerId).add(followeeId);
};

Twitter.prototype.unfollow = function(followerId, followeeId) {
    if (this.follows.has(followerId)) this.follows.get(followerId).delete(followeeId);
};

class Twitter {
    private time = 0;
    private tweets = new Map<number, number[][]>();
    private follows = new Map<number, Set<number>>();

    constructor() {
    }

    postTweet(userId: number, tweetId: number): void {
        this.time++;
        if (!this.tweets.has(userId)) this.tweets.set(userId, []);
        this.tweets.get(userId)!.push([this.time, tweetId]);
    }

    getNewsFeed(userId: number): number[] {
        const cand: number[][] = [];
        const users = new Set(this.follows.get(userId) || []);
        users.add(userId);
        for (const u of users)
            cand.push(...(this.tweets.get(u) || []).slice(-10));
        cand.sort((a, b) => b[0] - a[0]);
        return cand.slice(0, 10).map(x => x[1]);
    }

    follow(followerId: number, followeeId: number): void {
        if (followerId === followeeId)
            return;
        if (!this.follows.has(followerId)) this.follows.set(followerId, new Set());
        this.follows.get(followerId)!.add(followeeId);
    }

    unfollow(followerId: number, followeeId: number): void {
        if (this.follows.has(followerId)) this.follows.get(followerId)!.delete(followeeId);
    }
}

载入编辑器，自己跑一遍 →

其他解法

主解法把每人最近 10 条全部放在一起排序，写法简单；多路归并利用各列表的有序性，只取出真正需要的 10 条，不产生临时候选数组。

解法 2：多路归并时间 getNewsFeed O(10·F)，其余 O(1)，空间 O(T + E)

每个用户的推文列表按发布时间递增，天然有序。取关注列表和自己共 F 个用户，每人一个指针指向自己最新的推文。每轮在所有指针中选出时间最大的那条加入结果，并把该用户的指针前移一位。重复最多 10 轮。

不需要复制和排序候选推文，直接利用每个列表已有序的性质，是「合并 K 个有序链表」的应用。关注人数很多时，可以把每轮的线性选最大换成大根堆，降到 O(F + 10 log F)。

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = collections.defaultdict(list)
        self.follows = collections.defaultdict(set)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.time += 1
        self.tweets[userId].append((self.time, tweetId))

    def getNewsFeed(self, userId: int) -> List[int]:
        lists = [self.tweets[u] for u in self.follows[userId] | {userId}]
        ptr = [len(t) - 1 for t in lists]
        res = []
        while len(res) < 10:
            best = -1
            for i, t in enumerate(lists):
                if ptr[i] >= 0 and (best < 0 or t[ptr[i]][0] > lists[best][ptr[best]][0]):
                    best = i
            if best < 0:
                break
            res.append(lists[best][ptr[best]][1])
            ptr[best] -= 1
        return res

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.follows[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].discard(followeeId)

class Twitter {
    private int time = 0;
    private final Map<Integer, List<int[]>> tweets = new HashMap<>();
    private final Map<Integer, Set<Integer>> follows = new HashMap<>();

    public Twitter() {
    }

    public void postTweet(int userId, int tweetId) {
        time++;
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{time, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        List<List<int[]>> lists = new ArrayList<>();
        lists.add(tweets.getOrDefault(userId, new ArrayList<>()));
        for (int u : follows.getOrDefault(userId, new HashSet<>()))
            lists.add(tweets.getOrDefault(u, new ArrayList<>()));
        int[] ptr = new int[lists.size()];
        for (int i = 0; i < ptr.length; i++) ptr[i] = lists.get(i).size() - 1;
        List<Integer> res = new ArrayList<>();
        while (res.size() < 10) {
            int best = -1;
            for (int i = 0; i < ptr.length; i++) {
                if (ptr[i] >= 0 && (best < 0 || lists.get(i).get(ptr[i])[0] > lists.get(best).get(ptr[best])[0]))
                    best = i;
            }
            if (best < 0) break;
            res.add(lists.get(best).get(ptr[best])[1]);
            ptr[best]--;
        }
        return res;
    }

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

    public void unfollow(int followerId, int followeeId) {
        Set<Integer> s = follows.get(followerId);
        if (s != null) s.remove(followeeId);
    }
}

class Twitter {
    int time = 0;
    unordered_map<int, vector<pair<int, int>>> tweets;
    unordered_map<int, unordered_set<int>> follows;
public:
    Twitter() {}

    void postTweet(int userId, int tweetId) {
        time++;
        tweets[userId].push_back({time, tweetId});
    }

    vector<int> getNewsFeed(int userId) {
        vector<vector<pair<int, int>>*> lists;
        lists.push_back(&tweets[userId]);
        for (int u : follows[userId]) lists.push_back(&tweets[u]);
        vector<int> ptr;
        for (auto* t : lists) ptr.push_back((int)t->size() - 1);
        vector<int> res;
        while (res.size() < 10) {
            int best = -1;
            for (int i = 0; i < (int)lists.size(); i++) {
                if (ptr[i] >= 0 && (best < 0 || (*lists[i])[ptr[i]].first > (*lists[best])[ptr[best]].first))
                    best = i;
            }
            if (best < 0) break;
            res.push_back((*lists[best])[ptr[best]].second);
            ptr[best]--;
        }
        return res;
    }

    void follow(int followerId, int followeeId) {
        if (followerId != followeeId) follows[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        follows[followerId].erase(followeeId);
    }
};

type Twitter struct {
	time    int
	tweets  map[int][][2]int
	follows map[int]map[int]bool
}

func Constructor() Twitter {
	return Twitter{0, map[int][][2]int{}, map[int]map[int]bool{}}
}

func (this *Twitter) PostTweet(userId int, tweetId int) {
	this.time++
	this.tweets[userId] = append(this.tweets[userId], [2]int{this.time, tweetId})
}

func (this *Twitter) GetNewsFeed(userId int) []int {
	lists := [][][2]int{this.tweets[userId]}
	for u := range this.follows[userId] {
		lists = append(lists, this.tweets[u])
	}
	ptr := make([]int, len(lists))
	for i, t := range lists {
		ptr[i] = len(t) - 1
	}
	res := []int{}
	for len(res) < 10 {
		best := -1
		for i, t := range lists {
			if ptr[i] >= 0 && (best < 0 || t[ptr[i]][0] > lists[best][ptr[best]][0]) {
				best = i
			}
		}
		if best < 0 {
			break
		}
		res = append(res, lists[best][ptr[best]][1])
		ptr[best]--
	}
	return res
}

func (this *Twitter) Follow(followerId int, followeeId int) {
	if followerId == followeeId {
		return
	}
	if this.follows[followerId] == nil {
		this.follows[followerId] = map[int]bool{}
	}
	this.follows[followerId][followeeId] = true
}

func (this *Twitter) Unfollow(followerId int, followeeId int) {
	delete(this.follows[followerId], followeeId)
}

var Twitter = function() {
    this.time = 0;
    this.tweets = new Map();
    this.follows = new Map();
};

Twitter.prototype.postTweet = function(userId, tweetId) {
    this.time++;
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId).push([this.time, tweetId]);
};

Twitter.prototype.getNewsFeed = function(userId) {
    const users = new Set(this.follows.get(userId) || []);
    users.add(userId);
    const lists = [...users].map(u => this.tweets.get(u) || []);
    const ptr = lists.map(t => t.length - 1);
    const res = [];
    while (res.length < 10) {
        let best = -1;
        for (let i = 0; i < lists.length; i++) {
            if (ptr[i] >= 0 && (best < 0 || lists[i][ptr[i]][0] > lists[best][ptr[best]][0])) best = i;
        }
        if (best < 0) break;
        res.push(lists[best][ptr[best]][1]);
        ptr[best]--;
    }
    return res;
};

Twitter.prototype.follow = function(followerId, followeeId) {
    if (followerId === followeeId) return;
    if (!this.follows.has(followerId)) this.follows.set(followerId, new Set());
    this.follows.get(followerId).add(followeeId);
};

Twitter.prototype.unfollow = function(followerId, followeeId) {
    if (this.follows.has(followerId)) this.follows.get(followerId).delete(followeeId);
};

class Twitter {
    private time = 0;
    private tweets = new Map<number, number[][]>();
    private follows = new Map<number, Set<number>>();

    constructor() {
    }

    postTweet(userId: number, tweetId: number): void {
        this.time++;
        if (!this.tweets.has(userId)) this.tweets.set(userId, []);
        this.tweets.get(userId)!.push([this.time, tweetId]);
    }

    getNewsFeed(userId: number): number[] {
        const users = new Set<number>(this.follows.get(userId) || []);
        users.add(userId);
        const lists: number[][][] = [...users].map(u => this.tweets.get(u) || []);
        const ptr: number[] = lists.map(t => t.length - 1);
        const res: number[] = [];
        while (res.length < 10) {
            let best = -1;
            for (let i = 0; i < lists.length; i++) {
                if (ptr[i] >= 0 && (best < 0 || lists[i][ptr[i]][0] > lists[best][ptr[best]][0])) best = i;
            }
            if (best < 0) break;
            res.push(lists[best][ptr[best]][1]);
            ptr[best]--;
        }
        return res;
    }

    follow(followerId: number, followeeId: number): void {
        if (followerId === followeeId) return;
        if (!this.follows.has(followerId)) this.follows.set(followerId, new Set());
        this.follows.get(followerId)!.add(followeeId);
    }

    unfollow(followerId: number, followeeId: number): void {
        if (this.follows.has(followerId)) this.follows.get(followerId)!.delete(followeeId);
    }
}

设计专题的其他题目

查看设计全部题目 →