设计朋友圈时间线功能 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：设计朋友圈时间线功能

评论礼仪 见这里，违者直接拉黑。

[renektonwu]

大神，思路了解了，但是上面的代码通不过OJ系统

[renektonwu]

是我看走眼了，抱歉

[wxler]

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

[acearth]

没细看，但是：不需要post一次tw就关注自己一次，

[Xingyue0310]

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)

[yaoyuanyy]

最启发和精巧的部分：
Tweet twt = pq.poll();
res.add(twt.id);
// 将下一篇 Tweet 插入进行排序
if (twt.next != null)
pq.add(twt.next); // 这里最精巧了

[bruceeewong]

第一次做这种类型的题目，感觉好有成就感哈哈

[alizer]

# 用户取消关注一个人
def unfollow(self, userId: int):
    # 不可以取关自己
    if userId != self.id:
        self.followed.remove(userId)

这里有个小纰漏，需要加个判断条件

    # 用户取消关注一个人
    def unfollow(self, userId: int):
        # 不可以取关自己
        if userId != self.id and userId in self.followed:
            self.followed.remove(userId)