Medium

题目描述

给你一个整数 limit 和一个大小为 n x 2 的二维数组 queries。

有 limit + 1 个球，标签范围为 [0, limit]。最初，所有球都没有颜色。对于 queries 中形如 [x, y] 的每个查询，你需要将球 x 标记为颜色 y。在每次查询之后，你需要找出球中不同颜色的数量。

返回一个长度为 n 的数组 result，其中 result[i] 表示第 i 次查询后的颜色数量。

注意，在回答查询时，缺少颜色不会被视为一种颜色。

示例 1：

输入：limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]
输出：[1,2,2,3]
解释：
- 查询 0 后，球 1 有颜色 4。
- 查询 1 后，球 1 有颜色 4，球 2 有颜色 5。
- 查询 2 后，球 1 有颜色 3，球 2 有颜色 5。
- 查询 3 后，球 1 有颜色 3，球 2 有颜色 5，球 3 有颜色 4。

示例 2：

输入：limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]
输出：[1,2,2,3,4]
解释：
- 查询 0 后，球 0 有颜色 1。
- 查询 1 后，球 0 有颜色 1，球 1 有颜色 2。
- 查询 2 后，球 0 有颜色 1，球 1 和球 2 有颜色 2。
- 查询 3 后，球 0 有颜色 1，球 1 和球 2 有颜色 2，球 3 有颜色 4。
- 查询 4 后，球 0 有颜色 1，球 1 和球 2 有颜色 2，球 3 有颜色 4，球 4 有颜色 5。

约束条件：

  • 1 <= limit <= 10^9
  • 1 <= n == queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= queries[i][0] <= limit
  • 1 <= queries[i][1] <= 10^9

提示：

  • 使用两个哈希表来维护每个球的颜色和每种颜色对应的球集合。

解题思路

这道题需要动态维护球的颜色状态，并统计不同颜色的数量。关键在于处理球颜色的更新操作。

核心思路：

使用两个哈希表来高效管理颜色信息：

  1. ball_to_color：记录每个球当前的颜色
  2. color_to_balls：记录每种颜色对应的球集合

算法流程：

对于每个查询 [x, y]：

  1. 如果球 x 之前有颜色，需要从旧颜色的球集合中移除该球
  2. 如果移除后该颜色没有球了，需要删除这种颜色
  3. 将球 x 设置为新颜色 y
  4. 将球 x 添加到颜色 y 的球集合中
  5. 统计当前不同颜色的数量

这种方法的优势是能够精确跟踪每种颜色的使用状态，当某种颜色不再被任何球使用时能及时清理，保证颜色计数的准确性。

时间复杂度主要来自于哈希表的操作，每次查询的时间复杂度为 O(1)，总体效率很高。

代码实现

class Solution {
public:
    vector<int> queryResults(int limit, vector<vector<int>>& queries) {
        unordered_map<int, int> ball_to_color;
        unordered_map<int, unordered_set<int>> color_to_balls;
        vector<int> result;
        
        for (auto& query : queries) {
            int ball = query[0];
            int color = query[1];
            
            // If ball already has a color, remove it from old color
            if (ball_to_color.count(ball)) {
                int old_color = ball_to_color[ball];
                color_to_balls[old_color].erase(ball);
                if (color_to_balls[old_color].empty()) {
                    color_to_balls.erase(old_color);
                }
            }
            
            // Set new color for ball
            ball_to_color[ball] = color;
            color_to_balls[color].insert(ball);
            
            result.push_back(color_to_balls.size());
        }
        
        return result;
    }
};

class Solution:
    def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
        ball_to_color = {}
        color_to_balls = {}
        result = []
        
        for ball, color in queries:
            # If ball already has a color, remove it from old color
            if ball in ball_to_color:
                old_color = ball_to_color[ball]
                color_to_balls[old_color].remove(ball)
                if not color_to_balls[old_color]:
                    del color_to_balls[old_color]
            
            # Set new color for ball
            ball_to_color[ball] = color
            if color not in color_to_balls:
                color_to_balls[color] = set()
            color_to_balls[color].add(ball)
            
            result.append(len(color_to_balls))
        
        return result

public class Solution {
    public int[] QueryResults(int limit, int[][] queries) {
        Dictionary<int, int> ballToColor = new Dictionary<int, int>();
        Dictionary<int, HashSet<int>> colorToBalls = new Dictionary<int, HashSet<int>>();
        List<int> result = new List<int>();
        
        foreach (int[] query in queries) {
            int ball = query[0];
            int color = query[1];
            
            // If ball already has a color, remove it from old color
            if (ballToColor.ContainsKey(ball)) {
                int oldColor = ballToColor[ball];
                colorToBalls[oldColor].Remove(ball);
                if (colorToBalls[oldColor].Count == 0) {
                    colorToBalls.Remove(oldColor);
                }
            }
            
            // Set new color for ball
            ballToColor[ball] = color;
            if (!colorToBalls.ContainsKey(color)) {
                colorToBalls[color] = new HashSet<int>();
            }
            colorToBalls[color].Add(ball);
            
            result.Add(colorToBalls.Count);
        }
        
        return result.ToArray();
    }
}

var queryResults = function(limit, queries) {
    const ballColors = new Map();
    const colorCounts = new Map();
    const result = [];
    
    for (const [ball, color] of queries) {
        const oldColor = ballColors.get(ball);
        
        if (oldColor !== undefined) {
            const count = colorCounts.get(oldColor);
            if (count === 1) {
                colorCounts.delete(oldColor);
            } else {
                colorCounts.set(oldColor, count - 1);
            }
        }
        
        ballColors.set(ball, color);
        colorCounts.set(color, (colorCounts.get(color) || 0) + 1);
        
        result.push(colorCounts.size);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度值
时间复杂度O(n)
空间复杂度O(n)

其中 n 是查询的数量。每次查询的哈希表操作都是 O(1) 的平均时间复杂度，空间复杂度主要用于存储球与颜色的映射关系。

相关题目