ในปัญหานี้ เราได้รับอาร์เรย์ที่ประกอบด้วยค่าจำนวนเต็ม (2n+ 1) จากค่าทั้งหมดนี้มีองค์ประกอบ n รายการปรากฏขึ้นสองครั้งในอาร์เรย์และมีองค์ประกอบเพียงรายการเดียวในอาร์เรย์ ที่ปรากฏขึ้นครั้งเดียว งานของเราคือค้นหาซิงเกิ้ลในอาร์เรย์ขององค์ประกอบจำนวนเต็ม 2n+1
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {1, 3, 5, 6, 5, 1, 3} ผลลัพธ์
5
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการใช้ตัวนับสำหรับองค์ประกอบ หากพบองค์ประกอบ ให้เก็บค่าและจำนวนการเกิดขึ้น หลังจากนี้การค้นหาองค์ประกอบในตารางที่มีการนับ =1 โซลูชันที่มีประสิทธิภาพ .มากขึ้น จะใช้ XOR ที่นี่เราจะดำเนินการ XOR ขององค์ประกอบทั้งหมดของอาร์เรย์ XOR นี้จะทำให้องค์ประกอบทั้งหมดที่มีการเกิดสองครั้งเป็น 0 และองค์ประกอบเดียวที่มีค่าจะมีอยู่คือองค์ประกอบที่มีการเกิดเป็น 1
ทั้งนี้เป็นเพราะคุณสมบัติของ XOR ที่ −
- a^a = 0 - a^0 = a
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
The element of the array with single occurrence is 6
