Trong bài toán này, chúng ta được cung cấp một mảng gồm (2n + 1) giá trị nguyên. Trong tất cả các giá trị này, n phần tử xuất hiện hai lần trong mảng và chỉ có một phần tử duy nhất trong mảng xuất hiện một lần. Nhiệm vụ của chúng ta là Tìm đơn lẻ trong một mảng gồm 2n + 1 phần tử số nguyên.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {1, 3, 5, 6, 5, 1, 3} Đầu ra
5
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng bộ đếm cho các phần tử. Nếu một phần tử gặp phải, hãy lưu trữ giá trị và số lần xuất hiện của phần tử đó. Sau khi tìm kiếm phần tử trong bảng có số lần xuất hiện =1. Một giải pháp hiệu quả hơn sẽ sử dụng XOR. Ở đây, chúng ta sẽ thực hiện XOR tất cả các phần tử của mảng. XOR này sẽ làm cho tất cả các phần tử có lần xuất hiện kép bằng 0. Và phần tử duy nhất có giá trị sẽ hiện diện là phần tử có lần xuất hiện là 1.
Điều này là do các thuộc tính của XOR -
- a^a = 0 - a^0 = a
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
int findSingleValue(int arr[], int n) {
int element = 0;
for (int i = 0; i < n; i++)
element = element ^ arr[i];
return element;
}
int main() {
int arr[] = { 1, 3, 5, 6, 5, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The element of the array with single occurrence is "<<findSingleValue(arr, n);
return 0;
} Đầu ra
The element of the array with single occurrence is 6