C ++中的森林兔子

假设在森林中，每只兔子都有一些颜色。现在，兔子的一些子集（可能是全部）将告诉我们还有多少只兔子具有相同的颜色。这些答案放置在一个数组中。我们必须找到可能在森林中的兔子的最小数量。因此，如果输入类似于[1,1,2]，则输出将为5，因为两只回答“ 1”的兔子可能都是相同的颜色，例如白色。现在，兔子所回答的“ 2”不能为白色，否则答案将不一致。说回答“ 2”的兔子是黑色的。然后，在森林中应该有另外2只未对阵列做出反应的黑兔子。因此，森林中尽可能少的兔子数量是5：3回答了，再加上2没有回答。

为了解决这个问题，我们将遵循以下步骤-

• 制作一个映射m，n：=数组ans的大小

• 设置ret为0

• 对于i，范围为0至n – 1

• 将m [x]增加1

• 如果m [x] = x，则从m中删除x

• x：= ans [i]

• 如果x = 0，则将ret增加1，并跳过此迭代的下一部分。

• 如果m具有x，则将ret增加（x + 1），设置m [x]：= 0

• 除此以外

• 返回ret

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int numRabbits(vector<int>& ans) {
      map <int, int> m;
      int n = ans.size();
      int ret = 0;
      for(int i = 0; i < n; i++){
         int x = ans[i];
         if(x == 0){
            ret++;
            continue;
         }
         if(!m.count(x)){
            ret += (x + 1);
            m[x] = 0;
            }else{
               m[x]++;
           if(m[x] == x){
               m.erase(x);
            }
         }
      }
      return ret;
   }
};
main(){
   vector<int> v = {1,1,2};
   Solution ob;
   cout << (ob.numRabbits(v));
}

输入值

[1,1,2]

输出结果

5