题目

森林中有未知数量的兔子。提问其中若干只兔子 “还有多少只兔子与你（指被提问的兔子）颜色相同?” ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/rabbits-in-forest

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

两只相同颜色的兔子看到的其他同色兔子数必然是相同的。反之，若两只兔子看到的其他同色兔子数不同，那么这两只兔子颜色也不同。

因此，将 \textit{answers}answers 中值相同的元素分为一组，对于每一组，计算出兔子的最少数量，然后将所有组的计算结果累加，就是最终的答案。

例如，现在有 1313 只兔子回答 55。假设其中有一只红色的兔子，那么森林中必然有 66 只红兔子。再假设其中还有一只蓝色的兔子，同样的道理森林中必然有 66 只蓝兔子。为了最小化可能的兔子数量，我们假设这 1212 只兔子都在这 1313 只兔子中。那么还有一只额外的兔子回答 55，这只兔子只能是其他的颜色，这一颜色的兔子也有 66 只。因此这种情况下最少会有 1818 只兔子。

一般地，如果有 xx 只兔子都回答 yy，则至少有 \lceil\dfrac{x}{y+1}\rceil⌈
y+1
x
​
⌉ 种不同的颜色，且每种颜色有 y+1y+1 只兔子，因此兔子数至少为

\lceil\dfrac{x}{y+1}\rceil\cdot(y+1)
⌈
y+1
x
​
⌉⋅(y+1)

我们可以用哈希表统计 \textit{answers}answers 中各个元素的出现次数，对每个元素套用上述公式计算，并将计算结果累加，即为最终答案。

    int key;
    int val;
    UT_hash_handle hh;
};

int numRabbits(int* answers, int answersSize) {
    struct HashTable* hashTable = NULL;
    for (int i = 0; i < answersSize; i++) {
        struct HashTable* tmp;
        HASH_FIND_INT(hashTable, &answers[i], tmp);
        if (tmp == NULL) {
            tmp = malloc(sizeof(struct HashTable));
            tmp->key = answers[i];
            tmp->val = 1;
            HASH_ADD_INT(hashTable, key, tmp);
        } else {
            tmp->val++;
        }
    }
    int ans = 0;
    struct HashTable *iter, *tmp;
    HASH_ITER(hh, hashTable, iter, tmp) {
        int x = iter->val, y = iter->key;
        ans += (x + y) / (y + 1) * (y + 1);
    }
    return ans;
}