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