设计朋友圈时间线功能 :: labuladong的算法小抄 #1048
Replies: 7 comments 1 reply
-
大神,思路了解了,但是上面的代码通不过OJ系统 |
Beta Was this translation helpful? Give feedback.
-
是我看走眼了,抱歉 |
Beta Was this translation helpful? Give feedback.
-
355. 设计推特,时间复杂度O(n*k)这个思路貌似更容易理解,代码如下: class Twitter {
class Msg{
int tweetId,incId;//incId为全局唯一的自增id
public Msg(int t,int i){
tweetId=t;
incId=i;
}
}
//key:用户id,val:该用户关注的人
private HashMap<Integer,HashSet<Integer>> followMap;
//key:用户id,val:该用户发送的tweet
private HashMap<Integer,HashSet<Msg>> tweetMap;
private int incId=1;
public Twitter() {
this.followMap=new HashMap<>();
this.tweetMap=new HashMap<>();
}
public void postTweet(int userId, int tweetId) {
Msg msg=new Msg(tweetId,incId++);
if(tweetMap.containsKey(userId)){
tweetMap.get(userId).add(msg);
}else{
HashSet<Msg> ts=new HashSet<>();
ts.add(msg);
tweetMap.put(userId,ts);
}
follow(userId,userId);//关注自己
}
//时间复杂度:O(n*k),n为userId关注的用户数,k为该用户发送的tweet数
public List<Integer> getNewsFeed(int userId) {
List<Integer> list=new ArrayList<Integer>();
if(!followMap.containsKey(userId)) return list;
HashSet<Integer> allFollows=followMap.get(userId);
//queue:时间复杂度log(10)
PriorityQueue<Msg> queue=new PriorityQueue<>(new Comparator<Msg>(){
public int compare(Msg a,Msg b){
return a.incId-b.incId;//根据incId升序
}
});
for(int key:allFollows){
if(tweetMap.containsKey(key)){
for(Msg msg:tweetMap.get(key)) {
if(queue.size()==10) queue.poll();//移除小的
queue.offer(msg);
}
}
}
while(!queue.isEmpty()) list.add(queue.poll().tweetId);
//reverse:时间复杂度log(10)
Collections.reverse(list);
return list;
}
public void follow(int followerId, int followeeId) {
if(followMap.containsKey(followerId)){
followMap.get(followerId).add(followeeId);//关注他人
}else{
HashSet<Integer> set=new HashSet<>();
set.add(followeeId);//关注他人
followMap.put(followerId,set);
}
followMap.get(followerId).add(followerId);//关注自己
}
public void unfollow(int followerId, int followeeId) {
if(followMap.containsKey(followerId)){
followMap.get(followerId).remove(followeeId);
if(followMap.get(followerId).isEmpty()){
followMap.remove(followerId);
}
}
}
} |
Beta Was this translation helpful? Give feedback.
-
python 版本 class Tweet:
def __init__(self, tweetId, time):
self.tweetId = tweetId
self.time = time
self.next = None
def __lt__(self, other):
return (self.time > other.time)
class User:
def __init__(self, userId):
self.userId = userId
self.followed = set()
self.followed.add(userId)
self.tweets = None
def follow(self, followeeId):
self.followed.add(followeeId)
def unfollow(self, followeeId):
if followeeId != self.userId and followeeId in self.followed:
self.followed.remove(followeeId)
def post(self, tweetId, time):
new = Tweet(tweetId, time)
new.next = self.tweets
self.tweets = new
class Twitter:
import heapq
def __init__(self):
self.timestamp = 0
self.userMap = dict() # uderId --> User object
def postTweet(self, userId: int, tweetId: int) -> None:
# 若 userId 不存在,则新建
if userId not in self.userMap:
self.userMap[userId] = User(userId)
curUser = self.userMap[userId]
curUser.post(tweetId, self.timestamp)
self.timestamp += 1
def getNewsFeed(self, userId: int) -> List[int]:
if userId not in self.userMap:
return []
user = self.userMap[userId]
result = []
pq = []
followeeIds = list(user.followed)
for i in followeeIds:
t = self.userMap[i].tweets
if t:
heapq.heappush(pq, t)
while pq:
if len(result) == 10:
break
t = heapq.heappop(pq)
result.append(t.tweetId)
if t.next:
heapq.heappush(pq, t.next)
return result
def follow(self, followerId: int, followeeId: int) -> None:
# 若 follower 不存在,则新建
if followerId not in self.userMap:
self.userMap[followerId] = User(followerId)
# 若 followee 不存在,则新建
if followeeId not in self.userMap:
self.userMap[followeeId] = User(followeeId)
follower = self.userMap[followerId]
follower.follow(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
if followerId in self.userMap:
follower = self.userMap[followerId]
follower.unfollow(followeeId)
|
Beta Was this translation helpful? Give feedback.
-
最启发和精巧的部分: |
Beta Was this translation helpful? Give feedback.
-
第一次做这种类型的题目,感觉好有成就感哈哈 |
Beta Was this translation helpful? Give feedback.
-
这里有个小纰漏,需要加个判断条件
|
Beta Was this translation helpful? Give feedback.
-
文章链接点这里:设计朋友圈时间线功能
评论礼仪 见这里,违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions