Skip to content

Latest commit

 

History

History
216 lines (169 loc) · 6.93 KB

README.md

File metadata and controls

216 lines (169 loc) · 6.93 KB
Raw
comments difficulty edit_url rating source tags
true
中等
1517
第 131 场双周赛 Q3
数组
哈希表
模拟

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

English Version

题目描述

给你一个整数 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 <= 109
  • 1 <= n == queries.length <= 105
  • queries[i].length == 2
  • 0 <= queries[i][0] <= limit
  • 1 <= queries[i][1] <= 109

解法

方法一：双哈希表

我们使用一个哈希表 $\text{g}$ 记录每个球的颜色，使用一个哈希表 $\text{cnt}$ 记录每种颜色的球的个数。

接下来，遍历数组 $\text{queries}$，对于每个查询 $(x, y)$，我们将颜色 $y$ 的球的个数加 $1$，然后判断球 $x$ 是否已经染色，如果已经染色，我们将球 $x$ 的颜色的球的个数减 $1$，如果减到 $0$，我们将其从哈希表 $\text{cnt}$ 中移除。接下来，我们将球 $x$ 的颜色更新为 $y$，并将当前哈希表 $\text{cnt}$ 的大小加入答案数组。

遍历结束后，返回答案数组即可。

时间复杂度 $O(m)$，空间复杂度 $O(m)$，其中 $m$ 为数组 $\text{queries}$ 的长度。

Python3

class Solution:
    def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
        g = {}
        cnt = Counter()
        ans = []
        for x, y in queries:
            cnt[y] += 1
            if x in g:
                cnt[g[x]] -= 1
                if cnt[g[x]] == 0:
                    cnt.pop(g[x])
            g[x] = y
            ans.append(len(cnt))
        return ans

Java

class Solution {
    public int[] queryResults(int limit, int[][] queries) {
        Map<Integer, Integer> g = new HashMap<>();
        Map<Integer, Integer> cnt = new HashMap<>();
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            int x = queries[i][0], y = queries[i][1];
            cnt.merge(y, 1, Integer::sum);
            if (g.containsKey(x) && cnt.merge(g.get(x), -1, Integer::sum) == 0) {
                cnt.remove(g.get(x));
            }
            g.put(x, y);
            ans[i] = cnt.size();
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> queryResults(int limit, vector<vector<int>>& queries) {
        unordered_map<int, int> g;
        unordered_map<int, int> cnt;
        vector<int> ans;
        for (auto& q : queries) {
            int x = q[0], y = q[1];
            cnt[y]++;
            if (g.contains(x) && --cnt[g[x]] == 0) {
                cnt.erase(g[x]);
            }
            g[x] = y;
            ans.push_back(cnt.size());
        }
        return ans;
    }
};

Go

func queryResults(limit int, queries [][]int) (ans []int) {
	g := map[int]int{}
	cnt := map[int]int{}
	for _, q := range queries {
		x, y := q[0], q[1]
		cnt[y]++
		if v, ok := g[x]; ok {
			cnt[v]--
			if cnt[v] == 0 {
				delete(cnt, v)
			}
		}
		g[x] = y
		ans = append(ans, len(cnt))
	}
	return
}

TypeScript

function queryResults(limit: number, queries: number[][]): number[] {
    const g = new Map<number, number>();
    const cnt = new Map<number, number>();
    const ans: number[] = [];
    for (const [x, y] of queries) {
        cnt.set(y, (cnt.get(y) ?? 0) + 1);
        if (g.has(x)) {
            const v = g.get(x)!;
            cnt.set(v, cnt.get(v)! - 1);
            if (cnt.get(v) === 0) {
                cnt.delete(v);
            }
        }
        g.set(x, y);
        ans.push(cnt.size);
    }
    return ans;
}