หาตัวเลขที่ปรากฏครั้งเดียวในอาร์เรย์ขนาด 2n+1 ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ที่ประกอบด้วยค่าจำนวนเต็ม (2n+1) ค่า จากค่าทั้งหมดนี้ มี n องค์ประกอบที่ปรากฏสองครั้งในอาร์เรย์ และมีเพียงหนึ่งองค์ประกอบที่ปรากฏเพียงครั้งเดียว งานของเราคือ หาตัวเลขที่ปรากฏครั้งเดียวในอาร์เรย์ขนาด 2n+1

มาดูตัวอย่างเพื่อเข้าใจปัญหา

Input

arr[] = {1, 3, 5, 6, 5, 1, 3}

Output

6

วิธีแก้ปัญหา

วิธีแก้ที่ง่ายคือใช้ตัวนับสำหรับองค์ประกอบ ถ้าพบองค์ประกอบ ให้เก็บค่าและจำนวนครั้งที่เกิดขึ้น หลังจากนั้นค้นหาองค์ประกอบในตารางที่มีจำนวนครั้ง = 1 วิธีที่ มีประสิทธิภาพมากกว่า คือใช้ XOR ที่นี่ เราจะทำ XOR ขององค์ประกอบทั้งหมดในอาร์เรย์ XOR นี้จะทำให้องค์ประกอบที่เกิดขึ้นสองครั้งกลายเป็น 0 และองค์ประกอบที่มีการเกิดเพียงครั้งเดียวจะเหลือค่าไว้

เนื่องจากคุณสมบัติของ 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