สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม A ที่มีความยาวเท่ากัน ตอนนี้ เราต้องบอกว่าจริงก็ต่อเมื่อสามารถจัดลำดับใหม่ได้ในลักษณะที่ A[2 * i + 1] =2 * A[2 * i] สำหรับทุกๆ 0 <=i
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างแผนที่ m, n :=ขนาด A เก็บความถี่ของแต่ละองค์ประกอบใน A ลงในแผนที่ m
-
cnt :=ขนาด A
-
สำหรับแต่ละคู่คีย์-ค่า kv ในแผนที่
-
ถ้า m[คีย์ของ kv]> 0 แล้ว
-
ถ้า m[key of kv] ไม่ใช่ 0 และ m[2* key ของ kv]> 0
-
x :=นาทีของ m[คีย์ของ kv] และ m[2* คีย์ของ kv]
-
cnt :=cnt – (x * 2)
-
ลด m[2 * คีย์ kv] โดย x
-
ลด m[key of kv] โดย x
-
-
มิฉะนั้นเมื่อคีย์ของ kv =0 แล้ว
-
cnt :=cnt – m[คีย์ของ kv]
-
m[คีย์ของ kv] :=0
-
-
-
-
คืนค่า false เมื่อ cnt ไม่ใช่ศูนย์ มิฉะนั้น จะเป็น 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