# 3160. Find the Number of Distinct Colors Among the Balls

> ***View the book with <i class="fa fa-book"></i> Book Mode.***

- [**LeetCode筆記目錄**](https://hackmd.io/@WeiYee/SyABdj_eA)

## :book: 題目

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

## :dart: 解題步驟
- 因為 1 <= limit <= $10^9$，若使用 array 紀錄當前球的顏色會用太多記憶體，改成使用 Map (key:ball, value:color)，記錄當前球的顏色，沒有顏色的球不計。
- 再使用一個 Map (key:color, value:times) ，來記錄顏色及次數。
- 每一輪，先判斷是否有此球的先前紀錄，若無繼續下列動作，否則跳至下一步。
- 查閱 此球先前顏色的出現次數，若為 1，代表需要 remove 此值，否則 -1 更新值。
- 更新 2個 Map
- 所求是要每一輪有多少種顏色，那即為 Map (key:color, value:times) 的當前大小

## :pencil2: 程式碼
### Java

class Solution {
    public int[] queryResults(int limit, int[][] queries) {
                int i = 0;
        int[] ans = new int[queries.length];
        Map<Integer, Integer> ballColors = new HashMap<>();
        Map<Integer, Integer> colorCounts = new HashMap<>();
        for (int[] query : queries) {
            int ball = query[0];
            int currColor = query[1];
            if (ballColors.containsKey(ball)) {
                int prevColor = ballColors.get(ball);
                int prevColorCounts = colorCounts.get(prevColor) - 1;
                if (prevColorCounts == 0) colorCounts.remove(prevColor);
                else colorCounts.put(prevColor, prevColorCounts);
            }
            ballColors.put(ball, currColor);
            colorCounts.put(currColor, colorCounts.getOrDefault(currColor, 0) + 1);
            ans[i++] = colorCounts.size();
        }
        return ans;
    }
}