C++의 단일 숫자 III

배열이 ​​있다고 가정하면 정확히 두 개의 요소가 한 번 나타나지만 다른 요소는 두 번 나타납니다. 그래서 우리는 이 두 숫자를 찾을 함수를 정의해야 합니다. 따라서 주어진 배열이 [1,2,3,1,5,2]와 같으면 출력은 [3, 5]가 됩니다.

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

• xor_res :=0

• 범위 0에서 숫자 크기까지의 i에 대해

  • xor_res :=xor_res XOR 숫자[i]

• 위치 :=0

• 동안 xor_res AND 2^pos =0, 수행,

  • pos 1 증가

• num1 :=0

• 범위 0에서 숫자 – 1까지의 i에 대해

  • nums[i] 및 2 ^ pos가 0이 아니면

    • num1 :=num1 XOR num[i]

• num2 :=xor_res XOR num1

• num1 및 num2 반환

예시(C++)

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector <int> singleNumber(vector<int>& nums) {
      int xor_result = 0;
      for (int i=0;i < nums.size(); i++) {
         xor_result = xor_result ^ nums[i];
      }
      int pos = 0;
      while ((xor_result & (1 << pos)) == 0) {
         pos++;
      }
      int num1 = 0;
      for (int i=0;i < nums.size(); i++) {
         if ((nums[i] & (1 << pos)) != 0) {
            num1 = num1 ^ nums[i];
         }
      }
      int num2 = xor_result ^ num1;
      vector<int> result = {num1, num2};
      return result;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,1,3,2,5};
   print_vector(ob.singleNumber(v));
}

입력

[1,2,1,3,2,5]

출력

[3, 5, ]