C ++中的双对数组

假设我们有一个长度为偶数的整数A的数组，现在，当且仅当可能以A [2 * i + 1] = 2 * A [2 * i]重新排序时，我们才必须说true每0 <= i <len(A)/2。因此，如果输入类似于[3,1,3,6]，则结果为false，其中[4，-2,2，-4]为将返回true。

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

• 创建一个映射m，n：= A的大小，将A中每个元素的频率存储到映射m中

• cnt：= A的大小

• 对于映射中的每个键值对kv

• 如果m [kv的键]不为0并且m [2 * kv的键]> 0

• 否则，当kv = 0时，则

• x：= m [kv的键]和m [2 * kv的键]的最小值

• cnt：= cnt –（x * 2）

• 将m [2 * kv键]减少x

• 将m [kv的键]减少x

• cnt：= cnt – m [kv的键]

• m [kv的键]：= 0

• 如果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