781 森林中的兔子

· 2025-4-20   · 次阅读   · 字数统计: 126字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

781. 森林中的兔子

分析

思考题

如果有 $x$ 只兔子回答 $y$ ，则至少有 $\bigg\lceil\dfrac{x}{y+1}\bigg\rceil$ 不同的颜色，且每种颜色有 $y+1$ 只兔子

代码实现

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        unordered_map<int, int> cnt;
        int ans = 0;

        for(int i : answers) {
            cnt[i]++;
        }

        for(auto &[k, v] : cnt) {
            ans += (v + k) / (k + 1) * (k + 1);
        }

        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$