C++の森のウサギ

森の中で、それぞれのウサギが色を持っているとしましょう。これで、ウサギのサブセット（おそらくすべて）が、同じ色の他のウサギの数を教えてくれます。それらの答えは配列に配置されます。森にいる可能性のあるウサギの最小数を見つける必要があります。したがって、入力が[1,1,2]の場合、出力は5になります。これは、「1」と答えた2匹のウサギが同じ色、たとえば白である可能性があるためです。これで、「2」と答えたウサギを白くすることはできません。そうしないと、答えに一貫性がなくなります。 「2」と答えたウサギが黒だったとしましょう。次に、配列に応答しなかった他の2匹の黒いウサギが森にいるはずです。したがって、森の中のウサギの可能な最小数は5：3で、答えたのは2で、答えなかったのは2です。

これを解決するには、次の手順に従います-

• マップmを作成し、n：=配列ansのサイズ
• retを0に設定
• 0からn–1の範囲のiの場合
  • x：=ans [i]
  • x =0の場合、retを1増やし、この反復の次の部分をスキップします。
  • mにxがある場合は、retを（x + 1）増やし、m [x]：=0に設定します
  • それ以外の場合
    • m[x]を1増やします
    • m [x] =xの場合、mからxを削除します
• return 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