題目資訊

• 題目編號: 781
• 題目連結: Rabbits in Forest
• 主題: Array, Hash Table, Math, Greedy

題目敘述

有一個森林，裡面有不確定數量的兔子。我們問了 n 隻兔子**「有多少兔子的顏色和你一樣？」**，並將答案收集在整數數組 answers 中，其中 answers[i] 是第 $i$ 隻兔子的答案。

給定數組 answers，返回森林中可能存在的兔子的最小數量。

範例 1:

輸入: answers = [1,1,2]
輸出: 5
解釋:
回答「1」的兩隻兔子可能是相同顏色，比如紅色。
回答「2」的兔子不能是紅色，否則答案會不一致。
假設回答「2」的兔子是藍色。
那麼森林中應該有另外 2 隻藍色兔子沒有在數組中回應。
因此，森林中最小可能的兔子數為 5：3 隻有回答的加上 2 隻沒有回答的。

範例 2:

輸入: answers = [10,10,10]
輸出: 11

約束條件:

• $1 \leq \text{{answers.length}} \leq 1000$
• $0 \leq \text{{answers[i]}} < 1000$

直覺

此問題可被視為一個分組問題，其中每個獨特的回答代表一組相同顏色的兔子。關鍵在於理解回答相同數字的兔子可能屬於同一顏色組。每隻給出相同回答的兔子屬於一個包含其自身和其他未回答的相同顏色兔子的組別。任務是根據這些回答計算出最少兔子的數量，不僅要考慮那些回答的兔子，還要考慮根據每個回答的隱含意義，必須存在的兔子數量。

解法

為了求解這個問題，我們遵循以下步驟：

1. 使用映射計算頻率：

   • 遍歷給定的 answers 陣列，對於每一個回答，更新一個映射（countMap），以計算每個不同回答的出現次數。這使我們知道有多少兔子提供了相同的回答。

2. 計算最少兔子的數量：

   • 遍歷 countMap 中的每個條目。每個條目包含 answer（兔子所述的數字）和 count（給出該回答的兔子數量）。
   • 對於每個不同的 answer，我們知道所有提供該回答的兔子表示它們屬於由 answer + 1 隻兔子組成的一個組別（其自身加上未回答的相同顏色的其他兔子）。挑戰在於確定在給定的頻率 count 下需要多少這樣的組別。
   • 使用公式 ((count + answer) / (answer + 1)) 來計算需要多少完整的組別，確保向上取整。這是通過整數除法實現的：count + answer 確保任何餘數將因整數取整而強制增加一個組別。
   • 將所需組別的數量乘以該組別的大小 answer + 1 來確定該特定回答類別中兔子的總數量。

3. 累加總數：

   • 將每個不同回答計算出的兔子總數累加，以得到森林中兔子的最少數量。

通過遵循這種方法，我們確保所有的兔子都考慮在內，包括那些回答與根據所提供的回答邏輯推斷出的兔子。這些計算所產生的最終總數即為所需的結果。

程式碼

C++

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        int totalRabbits = 0; // 初始化兔子的總數。
        map<int, int> countMap; // 用來追蹤每個不同回答次數的地圖。

        // 計算每個不同回答的頻率。
        for (int answer : answers) {
            countMap[answer]++;
        }

        // 根據蒐集到的回答計算所需的最少兔子數量。
        for (auto& [answer, count] : countMap) {
            // 'answer + 1' 代表群組大小（相同顏色的兔子）。
            // 使用整數除法向上取整計算需要這樣的群組數量。
            // 乘以群組大小以獲得對於此回答的兔子總數。
            totalRabbits += (answer + 1) * ((count + answer) / (answer + 1));
        }

        return totalRabbits;
    }
};

Python

class Solution:
    def numRabbits(self, answers):
        totalRabbits = 0  # 初始化兔子的總數。
        countMap = {}  # 字典用來追蹤每個答案的數量。

        # 計算每個不同答案的頻率。
        for answer in answers:
            if answer in countMap:
                countMap[answer] += 1
            else:
                countMap[answer] = 1

        # 根據收集到的答案計算最少的兔子總數。
        for answer, count in countMap.items():
            # 'answer + 1' 代表同色兔子的群組大小。
            # 使用整數除法向上取整計算所需的群組數量。
            # 乘以群組大小以獲得這個答案對應的兔子總數。
            totalRabbits += (answer + 1) * ((count + answer) // (answer + 1))

        return totalRabbits

複雜度分析

• 時間複雜度: $O(n)$

  該解法主要涉及兩個迴圈：其中一個僅遍歷輸入陣列 answers 用於填充 countMap，而另一個則遍歷 countMap 中的唯一鍵。第一個迴圈需要 $O(n)$ 的時間，其中 $n$ 是 answers 陣列的長度。第二個迴圈遍歷每個在 answers 中至少出現一次的不同答案。在最壞情況下，如果所有元素均不同，該迴圈可能需要 $O(n)$ 的時間。因此，總的時間複雜度為 $O(n)$。

• 空間複雜度: $O(n)$

  演算法所使用的空間主要由 countMap 所佔用，這是一個存儲答案及其出現頻率的映射。在最壞情況下，如果 answers 陣列中的每個答案都是唯一的，則需要額外的 $O(n)$ 空間來存儲這些映射項。因此，空間複雜度為 $O(n)$。