1 <= userId, followerId, followeeId <= 5000 <= tweetId <= 10^4- 所有推特的 ID 都互不相同
-
postTweet、getNewsFeed、follow和unfollow方法最多调用3 * 10^4次
二、解题思路
-
使用一个数据结构来存储推文，可以使用列表或链表，列表中的每个元素代表一条推文，包含推文ID和用户ID。考虑到需要频繁地在头部插入新推文，使用链表结构更合适。
-
使用一个哈希表来存储用户关注关系，键为用户ID，值为该用户关注的所有用户ID集合。
-
postTweet方法：在推文链表的头部插入一条新推文。 -
getNewsFeed方法：遍历推文链表，找出当前用户和其关注用户的推文，按时间顺序排序，取前10条推文。 -
follow方法：在关注关系的哈希表中，将关注者ID添加到被关注者的关注者集合中。 -
unfollow方法：在关注关系的哈希表中，将关注者ID从被关注者的关注者集合中移除。
三、具体代码
import java.util.*;
public class Twitter {
private static class Tweet {
int time;
int tweetId;
Tweet next;
public Tweet(int time, int tweetId) {
this.time = time;
this.tweetId = tweetId;
this.next = null;
}
}
private Map<Integer, Set<Integer>> follows;
private Map<Integer, Tweet> tweets;
private int timeStamp;
public Twitter() {
follows = new HashMap<>();
tweets = new HashMap<>();
timeStamp = 0;
}
public void postTweet(int userId, int tweetId) {
Tweet newTweet = new Tweet(timeStamp++, tweetId);
newTweet.next = tweets.get(userId);
tweets.put(userId, newTweet);
}
public List<Integer> getNewsFeed(int userId) {
List<Tweet> list = new ArrayList<>();
// 添加当前用户的推文
if (tweets.containsKey(userId)) {
list.add(tweets.get(userId));
}
// 添加关注用户的推文
if (follows.containsKey(userId)) {
for (int followeeId : follows.get(userId)) {
if (tweets.containsKey(followeeId)) {
list.add(tweets.get(followeeId));
}
}
}
// 按时间排序
list.sort((a, b) -> b.time - a.time);
List<Integer> res = new ArrayList<>();
for (Tweet tweet : list) {
while (tweet != null && res.size() < 10) {
res.add(tweet.tweetId);
tweet = tweet.next;
}
}
return res;
}
public void follow(int followerId, int followeeId) {
follows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
if (follows.containsKey(followerId)) {
follows.get(followerId).remove(followeeId);
}
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
-
Twitter构造函数：- 初始化数据结构，时间复杂度为O(1)。
-
postTweet方法：- 每次调用时，直接在哈希表中插入新的推文节点，时间复杂度为O(1)。
-
getNewsFeed方法：- 遍历所有关注者的推文，最坏情况下，如果用户关注了所有其他用户，时间复杂度为O(N)，其中N是用户数量。
- 将所有推文节点加入列表，时间复杂度为O(N)。
- 对推文列表进行排序，时间复杂度为O(MlogM)，其中M是推文总数。
- 遍历排序后的推文列表以获取前10条推文，最坏情况下时间复杂度为O(M)。
- 综合起来，
getNewsFeed的时间复杂度为O(N + MlogM + M)。
-
follow方法：- 在哈希表中添加关注关系，时间复杂度为O(1)。
-
unfollow方法：- 在哈希表中移除关注关系，时间复杂度为O(1)。
2. 空间复杂度
-
Twitter构造函数：- 初始化了两个哈希表和一个整数，空间复杂度为O(N)，其中N是用户数量。
-
postTweet方法：- 每次调用时，创建一个新的推文节点，空间复杂度为O(1)。
-
getNewsFeed方法：- 创建了一个推文列表，最坏情况下，列表的大小为所有用户推文的总数M，空间复杂度为O(M)。
-
follow方法：- 在哈希表中添加关注关系，空间复杂度为O(1)。
-
unfollow方法：- 移除哈希表中的关注关系，空间复杂度为O(1)。
总体空间复杂度：
-
follows哈希表存储了所有用户的关注关系，空间复杂度为O(N^2)。 -
tweets哈希表存储了所有用户的推文，空间复杂度为O(M)。 - 因此，总体空间复杂度为O(N^2 + M)。
综上所述，该Twitter类的时间复杂度和空间复杂度分别为O(N + MlogM + M)和O(N^2 + M)。