ในปัญหานี้ เราได้รับ arr[] ขนาด N ที่มีค่าตั้งแต่ 1 ถึง N-1 โดยมีค่าหนึ่งค่าเกิดขึ้นสองครั้งในอาร์เรย์ งานของเราคือ ค้นหาองค์ประกอบที่ทำซ้ำเพียงอย่างเดียวในอาร์เรย์ที่จัดเรียงขนาด n .
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
arr[] = {1, 2, 3, 4, 5, 5, 6, 7} ผลผลิต
5
แนวทางการแก้ปัญหา
วิธีง่ายๆ ในการแก้ปัญหาคือการใช้การค้นหาเชิงเส้นและตรวจสอบว่า arr[i] และ arr[i+1] มีค่าเท่ากันหรือไม่ ในกรณีนี้ ให้คืนค่า arr[i] ซึ่งเป็นค่าที่ซ้ำกัน
ตัวอย่างที่ 1
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int findRepeatingValueArr(int arr[], int N){
for(int i = 0; i < N; i++){
if(arr[i] == arr[i+1])
return (arr[i]);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 4, 5, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, N);
return 0;
} ผลลัพธ์
The repeating value in the array is 4
อีกวิธีในการแก้ปัญหาคือการใช้อัลกอริทึมการค้นหาแบบไบนารีเพื่อค้นหาองค์ประกอบที่เกิดขึ้นสองครั้งที่ดัชนีกลาง หากค่าดัชนีกลางซ้ำแล้วซ้ำอีก ให้พิมพ์ออกมา หากไม่อยู่ที่ตำแหน่งดัชนี ให้ข้ามอาร์เรย์ย่อยด้านขวา มิฉะนั้น ให้ข้ามอาร์เรย์ย่อยด้านซ้าย
ตัวอย่างที่ 2
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
int findRepeatingValueArr(int arr[], int s, int e){
if (s > e)
return -1;
int mid = (s + e) / 2;
if (arr[mid] != mid + 1){
if (mid > 0 && arr[mid]==arr[mid-1])
return arr[mid];
return arr[findRepeatingValueArr(arr, s, mid-1)];
}
return arr[findRepeatingValueArr(arr, mid+1, e)];
}
int main(){
int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, 0, n-1);;
return 0;
} ผลลัพธ์
The repeating value in the array is 6
