Cho mảng A độ dài chẵn, kiểm tra có thể sắp xếp lại sao cho A[2*i+1] = 2*A[2*i] với mọi i không.
Ví dụ: [3,1,3,6] → false; [4,-2,2,-4] → true (có thể ghép -2&-4, 2&4).
Giải pháp:
Đếm tần suất mỗi số vào map
Duyệt các key theo thứ tự tăng dần (map tự sắp xếp):
Nếu key ≠ 0 và freq[key]>0 và freq[2*key]>0:
x = min(freq[key], freq[2*key])
Giảm cả hai freq xuống x, cnt -= 2*x
Nếu key = 0: cnt -= freq[0], freq[0]=0Trả về cnt == 0
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: bool canReorderDoubled(vector<int>& A) { map <int, int> m; for(int x : A) m[x]++; int cnt = A.size(); for(auto it = m.begin(); it != m.end(); ++it){ 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 -= 2*x; m[it->first*2] -= x; m[it->first] -= x; }else if(it->first == 0){ cnt -= m[it->first]; m[it->first] = 0; } } } return !cnt; } }; int main(){ vector<int> v1 = {3,1,3,6}; Solution ob; cout << ob.canReorderDoubled(v1) << endl; v1 = {4,-2,2,-4}; cout << ob.canReorderDoubled(v1); }Đầu vào
[3,1,3,6] [4,-2,2,-4]
Đầu ra
0 1