Mảng các cặp đôi trong C ++

Giả sử chúng ta có một mảng các số nguyên A với độ dài chẵn, bây giờ chúng ta phải nói đúng nếu và chỉ khi có thể sắp xếp lại nó theo cách A [2 * i + 1] =2 * A [2 * i] với mọi 0 <=i

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một bản đồ m, n:=kích thước của A, lưu trữ tần số của từng phần tử trong A vào bản đồ m

• cnt:=kích thước của A

• cho mỗi cặp khóa-giá trị kv trong bản đồ

  • nếu m [khóa của kv]> 0, thì

    • nếu m [khóa của kv] không phải là 0 và m [2 * khóa của kv]> 0

      • x:=min of m [key of kv] và m [2 * key of kv]

      • cnt:=cnt - (x * 2)

      • giảm m [2 * khóa của kv] x

      • giảm m [khóa của kv] x

    • ngược lại khi khóa của kv =0 thì

      • cnt:=cnt - m [khóa của kv]

      • m [khóa của kv]:=0

• trả về false khi cnt khác 0, ngược lại là true

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

0
1