[LeetCode]Rabbits in Forest

题目的描述可以观察出来，如果两个兔子的颜色一样，那么他们报的数字一定一样。但是反过来不一定。那么我们如何确定报相同数字的兔子他们是否拥有相同的颜色呢？根据题目的要求，我们要让兔子的总数越小越好，假设有n个兔子报的数字为m，有以下几种情况：

• n < m + 1, 为了让兔子总数最小，我们可以让这n个兔子都有相同的颜色c，颜色为c的兔子总数根据报数有m + 1个(包括报数者自己)
• n == m + 1同理，n个兔子可以有相同的颜色c，颜色为c的兔子总共有m + 1个
• n > m + 1, 我们可以先让m + 1个兔子有相同的颜色，更新n = n - (m + 1)，继续算，直到n小于等于0

常数空间，假设总共有n个兔子，时间复杂度O(n)，代码如下：

	class Solution {
	public:
	int numRabbits(vector<int>& answers) {
	int len = answers.size(), res = 0;
	unordered_map<int, int> map;
	for (int& count : answers)++map[count];
	for (auto& p : map)
	{
	int minNum = p.first + 1;
	while (p.second > 0)
	{
	res += minNum;
	p.second -= minNum;
	}
	}
	return res;
	}
	};

view raw Rabbits in Forest.cpp hosted with ❤ by GitHub