100313. 所有球里面不同颜色的数目

题目描述

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

总共有 limit + 1 个球，每个球的编号为 [0, limit] 中一个 互不相同 的数字。一开始，所有球都没有颜色。queries 中每次操作的格式为 [x, y] ，你需要将球 x 染上颜色 y 。每次操作之后，你需要求出所有球中 不同 颜色的数目。

请你返回一个长度为 n 的数组 result ，其中 result[i] 是第 i 次操作以后不同颜色的数目。

注意 ，没有染色的球不算作一种颜色。

思路

见注释

代码

class Solution {
public:
    vector<int> queryResults(int limit, vector<vector<int>>& queries) { 
        vector<int> result;
        
        unordered_map<int,int> map;  //存储球的编号和颜色
        unordered_map<int,int> colors;  //存储颜色的数量
        
        for(int i = 0;i < queries.size();i++){  //初始化
            colors[queries[i][1]] = 0;
            map[queries[i][0]] = 0;
        }

        int count = 0;
              
        for(int i = 0;i < queries.size();i++){
        //任何情况下，给一个球染色，该球的颜色置为color，该颜色的数量增加
            int idx = queries[i][0];
            int color = queries[i][1];
            
            if(map[idx] == 0 && colors[color] == 0){
           //给一个未染过色的球染上新的颜色，不同颜色球的数量增加
                count++;
                map[idx] = color;
                colors[color]++;
            }else if(map[idx] == 0){
           //给一个未染过色的球染上已经存在的颜色，不同颜色球的数量不会增加
                map[idx] = color;
                colors[color]++;
            }else if(colors[color] != 0 && map[idx] != color){
            //给一个染过色的球染上已经存在的颜色，球原有的颜色数量减少，如果减至0，那么存在的颜色会少一种，不同颜色球的数量会减少
                colors[map[idx]]--;
                if(colors[map[idx]] == 0){
                    count--;
                }
                colors[color]++;
                map[idx] = color;
            }else if(colors[color] == 0){
          //给一个染过色的球染上新的颜色，球原有的颜色数量减少，如果减至0，旧颜色少一种，新颜色多一种，不同颜色球的数量不变。否则，不同颜色球的数量会增加
                colors[color]++;
                colors[map[idx]]--;
                if(colors[map[idx]] != 0){
                    count++;
                }
                map[idx] = color;
            }
          //染完色后存储不同球颜色的数量
            result.push_back(count);
        }
        return result;
    }
};