C++의 이중 쌍 배열

<시간/>

길이가 짝수인 정수 A의 배열이 있다고 가정하고 A[2 * i + 1] =2 * A[2 * i]와 같은 방식으로 재정렬할 수 있는 경우에만 true라고 말해야 합니다. 모든 0 <=i

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

맵 생성 m, n :=A의 크기, A에 있는 각 요소의 빈도를 맵 m에 저장
cnt :=A의 크기
맵의 각 키-값 쌍 kv에 대해
- m[kv의 키]> 0이면
  - m[kv의 키]가 0이 아니고 m[2* kv의 키]> 0
    인 경우
    - x :=m[kv의 키] 및 m[2* kv의 키]의 최소값
    - cnt :=cnt – (x * 2)
    - m[2 * kv의 키] x
      감소
    - m[kv의 키]를 x만큼 감소
  - 그렇지 않으면 kv의 키가 0이면
    - cnt :=cnt – m[kv의 키]
    - m[kv의 키] :=0
cnt가 0이 아니면 false를 반환하고, 그렇지 않으면 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