ในปัญหานี้ เราได้รับ arr[] ขนาด n งานของเราคือ f ระบุองค์ประกอบที่แตกต่างกันเพียงรายการเดียวในอาร์เรย์ .
มีองค์ประกอบที่แตกต่างกันเพียงสองประเภทในอาร์เรย์ องค์ประกอบทั้งหมดเหมือนกันยกเว้นหนึ่งรายการ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
arr[] = {1, 1, 1, 2, 1, 1, 1, 1} ผลผลิต
2
แนวทางการแก้ปัญหา
แนวทางง่ายๆ ในการแก้ปัญหาคือเราต้องสำรวจอาร์เรย์และค้นหาองค์ประกอบที่แตกต่างจากองค์ประกอบอื่นๆ ของอาร์เรย์ วิธีการนี้ต้องการความซับซ้อนของเวลาของ O(N 2 )
อีกวิธีในการแก้ปัญหาใน O(N) คือการใช้ตารางแฮชเพื่อจัดเก็บองค์ประกอบและความถี่ในการเกิดขึ้น และพิมพ์ค่าด้วยความถี่เดียวที่เกิดขึ้น
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int findDiffElementArray(int arr[], int n){
if (n == 1)
return -1;
if (n == 2)
return arr[0];
if (arr[0] == arr[1] && arr[0] != arr[2])
return arr[2];
if (arr[0] == arr[2] && arr[0] != arr[1])
return arr[1];
if (arr[1] == arr[2] && arr[0] != arr[1])
return arr[0];
for (int i = 3; i < n; i++)
if (arr[i] != arr[i - 1])
return arr[i];
return -1;
}
int main(){
int arr[] = { 5, 5, 1, 5, 5, 5, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The different element in the array is "<<findDiffElementArray(arr, n);
return 0;
} ผลลัพธ์
The different element in the array is 1
