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