Array of Doubled Pairs ใน C++

คำอธิบายปัญหา

กำหนดอาร์เรย์ A ความยาวคู่ ต้องการจัดเรียงใหม่ได้หรือไม่ ที่ A[2*i+1] = 2 * A[2*i] สำหรับทุก i

ตัวอย่าง: [3,1,3,6] → false, [4,-2,2,-4] → true (จับคู่ -2&-4, 2&4)

วิธีแก้ปัญหา (Greedy + Hash Map)

1. นับความถี่แต่ละตัวเลข
2. เรียงลำดับ key (จัดการลบได้ถูกต้อง)
3. สำหรับแต่ละ key x (จากน้อยไปมาก):
4. ถ้า freq[x] > 0 ต้องจับคู่กับ 2x
5. ลด freq[x] และ freq[2x] ตามจำนวนคู่
6. กรณี x=0: ต้องมี freq[0] เป็นเลขคู่

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool canReorderDoubled(vector<int>& A) {
        map<int, int> freq;
        for(int x : A) freq[x]++;
        
        for(auto& [x, cnt] : freq) {
            if(cnt == 0) continue;
            if(x == 0) {
                if(cnt % 2 != 0) return false;
            } else {
                int need = cnt;
                if(freq[2*x] < need) return false;
                freq[2*x] -= need;
            }
        }
        return true;
    }
};

int main() {
    vector<int> v1 = {3,1,3,6};
    Solution ob;
    cout << ob.canReorderDoubled(v1) << endl; // 0
    v1 = {4,-2,2,-4};
    cout << ob.canReorderDoubled(v1); // 1
    return 0;
}

อินพุต

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

เอาต์พุต

0 1