ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด N มีค่าตั้งแต่ 1 ถึง N-1 พร้อมกับค่าหนึ่งเกิดขึ้นสองครั้งในอาร์เรย์ ภารกิจของเราคือ หาองค์ประกอบที่ซ้ำเพียงอย่างเดียวในอาร์เรย์ที่จัดเรียงแล้วขนาด n
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
arr[] = {1, 2, 3, 4, 5, 5, 6, 7}
เอาต์พุต
5
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการใช้ linear search และตรวจสอบว่า 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
อีกวิธีหนึ่งในการแก้ปัญหาคือการใช้ binary search algorithm เพื่อหาองค์ประกอบที่เกิดขึ้นสองครั้งที่ดัชนี mid หากค่าที่ดัชนีกลางซ้ำตัวเอง ให้พิมพ์มัน ถ้ามันไม่อยู่ที่ตำแหน่งดัชนี ให้เดินทางไปยัง subarray ขวา มิฉะนั้นเดินทางไปยัง subarray ซ้าย
ตัวอย่าง 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
