Một phần tử trong một mảng được sắp xếp trong C ++

Giả sử chúng ta có một mảng đã sắp xếp chỉ gồm các số nguyên trong đó mọi phần tử xuất hiện chính xác hai lần, ngoại trừ một phần tử xuất hiện đúng một lần. chúng ta phải tìm phần tử duy nhất này chỉ xuất hiện một lần. Vì vậy, nếu mảng giống như [1, 1, 2, 3, 3, 4, 4, 8, 8], thì đầu ra sẽ là 2

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

• ans:=0
• cho tôi trong phạm vi từ 0 đến kích thước mảng nums
  • ans:=ans XOR nums [i]
  • trả lại ans

Ví dụ (C ++)

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

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

Đầu vào

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

Đầu ra

2