ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n ภารกิจของเราคือ หาองค์ประกอบที่ต่างออกไปเพียงอย่างเดียวในอาร์เรย์
มีเพียงสองประเภทขององค์ประกอบที่แตกต่างกันในอาร์เรย์ ทุกองค์ประกอบเหมือนกันยกเว้นหนึ่ง
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
arr[] = {1, 1, 1, 2, 1, 1, 1, 1}
เอาต์พุต
2
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายในการแก้ปัญหา เราต้องเดินทางผ่านอาร์เรย์และหาองค์ประกอบที่แตกต่างจากองค์ประกอบอื่นๆ ของอาร์เรย์ วิธีนี้ต้องการความซับซ้อนของเวลา O(N2)
อีกวิธีหนึ่งในการแก้ปัญหาใน 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
