今日题目

https://leetcode.com/problems/find-the-number-of-distinct-colors-among-the-balls/description

解题思路

我们只需要知道当前列表中有多少种颜色即可。 为此，记录每种颜色对应的球的数量。 若某颜色的球数量变为 0，则 col_cnt -= 1。 若出现了新颜色，则 col_cnt += 1。

方法

  • 为每个球和每种颜色维护一个哈希表。
  • 修改某个球的颜色。
  • 若该颜色的球数量变为 0，则 col_cnt -= 1。
  • 若出现了新颜色，则 col_cnt += 1。

复杂度

  • 时间复杂度：$O(N)$，N 为查询数组的长度。

  • 空间复杂度：$O(N)$，N 为查询数组的长度。

潜在的进阶问题

如果现在需要修改一段区间内球的颜色？ 例如，输入变为 (x, y, z)，将编号从 x 到 y（含两端）的球的颜色全部改为 z。 然后询问此时有多少种不同颜色的球？

代码

class Solution:
    def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
        col = 0
        ans = []
        visCol = dict()
        balCol = dict()
        for (x, y) in queries:
            if x in balCol:
                visCol[balCol[x]] -= 1
                if visCol[balCol[x]] == 0:
                    col -= 1
            balCol.update({x: y})
            if (y not in visCol) or (visCol[y] == 0):
                col += 1
                visCol.update({y: 1})
            else:
                visCol[y] += 1
        
            ans.append(col)
        
        return ans

image.png