하위 배열을 부정한 후 얻을 수 있는 고유한 값의 수를 찾는 C++ 프로그램

<시간/>

n개의 요소가 있는 배열 A가 있다고 가정합니다. 주어진 숫자의 하위 집합을 선택하고 이 숫자를 무효화합니다. 우리는 얻을 수 있는 배열에서 서로 다른 값의 최대 수를 찾아야 합니다.

따라서 입력이 A =[1, 1, 2, 2]와 같으면 출력은 4가 됩니다. 네 가지 다른 값.

단계

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

Define one set se
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   x := A[i]
   if x is present in se, then:
      insert -x into se
   Otherwise
      insert x into se
return size of se

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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

int solve(vector<int> A) {
   set<int> se;
   int n = A.size();
   for (int i = 0; i < n; i++) {
      int x = A[i];
      if (se.count(x))
         se.insert(-x);
      else
         se.insert(x);
   }
   return se.size();
}
int main() {
   vector<int> A = { 1, 1, 2, 2 };
   cout << solve(A) << endl;
}

입력

{ 1, 1, 2, 2 }