牡丹江市网站建设_网站建设公司_在线商城_seo优化

Problem: 781. Rabbits in Forest 森林中的兔子

解题过程

耗时100%，回答相同的兔子可能是相同颜色的，像 3 3 3 3，那么这4个兔子刚好是相同颜色，像3 3 3 3 3，那么只有其中4个兔子相同颜色，另外一只颜色不同，至少需要8只兔子，像2至少3只兔子，2 2至少3只，2 2 2至少3只，2 2 2 2至少6只，也就是相同数字的统计值除以（数字+1）取上界ceil()

所以对数组做排序，然后用哈希表统计相同回答的数量，最后用公式计算结果并累加：ret += (int)ceil( ans[i] / (float)(i + 1.0f) ) * ( i + 1 ); i就是回答的数字，ceil向上取整的

Code

class Solution { public: int ans[1001]; int numRabbits(vector<int>& answers) { sort(answers.begin(), answers.end()); memset(ans, 0, sizeof(ans)); int ret = 0; for(int i = 0; i < answers.size(); i++) { ans[answers[i]]++; } for(int i = 0; i < 1001; i++) { if(ans[i] > 0) { ret += (int)ceil( ans[i] / (float)(i + 1.0f) ) * ( i + 1 ); } } return ret; } };