C++에서 정렬된 배열의 단일 요소

정확히 한 번 나타나는 하나의 요소를 제외하고 모든 요소가 정확히 두 번 나타나는 정수로만 구성된 정렬된 배열이 있다고 가정합니다. 한 번만 나타나는 이 단일 요소를 찾아야 합니다. 따라서 배열이 [1, 1, 2, 3, 3, 4, 4, 8, 8]과 같으면 출력은 2

가 됩니다.

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

ans :=0
0에서 nums 배열 크기 범위에 있는 i의 경우
- ans :=ans XOR 숫자[i]
- 반환

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int singleNonDuplicate(vector<int>& nums) {
      int ans = 0;
      for(int i = 0;i < nums.size(); i++)ans ^= nums[i];
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,2,3,3,4,4,8,8};
   cout << (ob.singleNonDuplicate(v));
}

입력

[1,1,2,3,3,4,4,8,8]