ค้นหาเฉพาะองค์ประกอบที่ซ้ำกันระหว่าง 1 ถึง n-1 โดยใช้ C++

ในปัญหานี้ เราได้รับอาร์เรย์ที่ไม่เรียงลำดับ 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) ออกจากผลรวมอาร์เรย์

ผลรวมของ 1 ^st จำนวนธรรมชาติ N-1 (S_n ) =n*(n-1)/2

doubleVal =arrSum - (S_n .) )

ตัวอย่างที่ 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