LeetCode 355. 设计推特

Categories:

题目描述
思路分析
1. 解法一：哈希表 + 优先队列（推荐）
相似题目

题目描述

✅ 355. 设计推特

思路分析

解法一：哈希表 + 优先队列（推荐）

核心思路：

用哈希表维护每个用户的关注列表（followMap）和推文列表（tweetMap）

每条推文记录全局时间戳，数值越大越新

getNewsFeed 时，将自己和所有关注者的最新推文加入最大堆，按时间戳降序弹出最多 10 条

优先队列中存储 [timestamp, userId, index]，每次弹出后将该用户下一条推文继续入堆

复杂度分析：

时间复杂度：O(F·log F + 10·log F)，其中 F 表示关注者数量，每次 getNewsFeed 最多操作 10 次堆

空间复杂度：O(U·T + U·F)，其中 U 表示用户数，T 表示推文数，F 表示关注关系数

import java.util.ArrayList;
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 int timestamp = 0;

  // 每个用户的推文列表，存储 [timestamp, tweetId]
  private Map<Integer, List<int[]>> tweetMap = new HashMap<>();

  // 每个用户的关注列表
  private Map<Integer, Set<Integer>> followMap = new HashMap<>();

  public Twitter() {}

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

  public List<Integer> getNewsFeed(int userId) {
    // 最大堆：按时间戳降序
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);

    // 将自己的最新推文入堆
    addLatestTweet(pq, userId);

    // 将所有关注者的最新推文入堆
    Set<Integer> following = followMap.getOrDefault(userId, new HashSet<>());
    for (int followeeId : following) {
      addLatestTweet(pq, followeeId);
    }

    List<Integer> result = new ArrayList<>();
    while (!pq.isEmpty() && result.size() < 10) {
      int[] top = pq.poll();
      result.add(top[1]);

      // 继续将该用户的下一条推文入堆
      int nextIndex = top[2] - 1;
      if (nextIndex >= 0) {
        List<int[]> tweets = tweetMap.get(top[3]);
        pq.offer(new int[]{tweets.get(nextIndex)[0], tweets.get(nextIndex)[1], nextIndex, top[3]});
      }
    }

    return result;
  }

  // 将指定用户最新一条推文入堆，存储 [timestamp, tweetId, index, userId]
  private void addLatestTweet(PriorityQueue<int[]> pq, int userId) {
    List<int[]> tweets = tweetMap.get(userId);
    if (tweets != null && !tweets.isEmpty()) {
      int idx = tweets.size() - 1;
      pq.offer(new int[]{tweets.get(idx)[0], tweets.get(idx)[1], idx, userId});
    }
  }

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

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

import "container/heap"

type Twitter struct {
    timestamp int
    // tweetMap[userId] = [][2]int{timestamp, tweetId}
    tweetMap  map[int][][2]int
    // followMap[userId] = set of followeeIds
    followMap map[int]map[int]bool
}

func Constructor() Twitter {
    return Twitter{
        tweetMap:  make(map[int][][2]int),
        followMap: make(map[int]map[int]bool),
    }
}

func (t *Twitter) PostTweet(userId int, tweetId int) {
    t.tweetMap[userId] = append(t.tweetMap[userId], [2]int{t.timestamp, tweetId})
    t.timestamp++
}

// 堆中元素：[timestamp, tweetId, index, userId]
type Item [4]int

type MaxHeap []Item

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i][0] > h[j][0] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func (t *Twitter) GetNewsFeed(userId int) []int {
    h := &MaxHeap{}
    heap.Init(h)

    // 添加自己及所有关注者的最新推文
    users := []int{userId}
    for followeeId := range t.followMap[userId] {
        users = append(users, followeeId)
    }

    for _, uid := range users {
        tweets := t.tweetMap[uid]
        if len(tweets) > 0 {
            idx := len(tweets) - 1
            heap.Push(h, Item{tweets[idx][0], tweets[idx][1], idx, uid})
        }
    }

    result := make([]int, 0, 10)
    for h.Len() > 0 && len(result) < 10 {
        top := heap.Pop(h).(Item)
        result = append(result, top[1])

        // 继续将该用户的下一条推文入堆
        nextIdx := top[2] - 1
        if nextIdx >= 0 {
            uid := top[3]
            tweets := t.tweetMap[uid]
            heap.Push(h, Item{tweets[nextIdx][0], tweets[nextIdx][1], nextIdx, uid})
        }
    }

    return result
}

func (t *Twitter) Follow(followerId int, followeeId int) {
    if t.followMap[followerId] == nil {
        t.followMap[followerId] = make(map[int]bool)
    }
    t.followMap[followerId][followeeId] = true
}

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

相似题目

题目	难度	考察点
23. 合并 K 个升序链表	困难	优先队列、链表
295. 数据流的中位数	困难	堆、设计
703. 数据流中的第 K 大元素	简单	堆、设计
346. 数据流中的移动平均值	简单	队列、设计
981. 基于时间的键值存储	中等	哈希表、二分查找、设计
362. 敲击计数器	中等	队列、设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/62239190