อาร์เรย์ของคู่คู่ใน C++

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม 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