C++での2倍のペアの配列

整数Aの配列が偶数の長さであるとすると、A [2 * i + 1] =2 * A [2 * i]のように並べ替えることができる場合に限り、trueと言わなければなりません。 for every 0 <=i

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

• マップm、n：=Aのサイズを作成し、Aの各要素の頻度をマップmに保存します

• cnt：=Aのサイズ

• マップ内のキーと値のペアkvごとに

  • m[kvのキー]>0の場合、

    • m [kvのキー]が0でなく、m[2*kvのキー]>0

      の場合

      • x：=m[kvのキー]とm[2*kvのキー]の最小値

      • cnt：=cnt –（x * 2）

      • m [2*kvのキー]をxだけ減らします

      • m[kvのキー]をxだけ減らします

    • それ以外の場合、kv =0のキーの場合、

      • cnt：=cnt –m[kvのキー]

      • m [kvのキー]：=0

• cntがゼロ以外の場合はfalseを返し、それ以外の場合はtrueを返します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool canReorderDoubled(vector<int>& A) {
      map <int, int> m;
      int n = A.size();
      for(int i = 0; i < n; i++){
         m[A[i]]++;
      }
      int cnt = A.size();
      map <int, int> :: iterator it = m.begin();
      while(it != m.end()){
         if(m[it->first] > 0){
            if(it->first != 0 && m[it->first * 2] > 0){
               int x = min(m[it->first], m[it->first * 2]);
               cnt -= (x * 2);
               m[it->first * 2] -= x;
               m[it->first] -= x;
            }else if(it->first == 0){
               cnt -= m[it->first];
               m[it->first] = 0;
            }
         }
         it++;
      }
      return !cnt;
   }
};
main(){
   vector<int> v1 = {3,1,3,6};
   Solution ob;
   cout << (ob.canReorderDoubled(v1)) << endl;
   v1 = {4,-2,2,-4};
   cout << (ob.canReorderDoubled(v1));
}

入力

[3,1,3,6]
[4,-2,2,-4]

出力

0
1