ค้นหาดัชนีขององค์ประกอบพิเศษที่มีอยู่ในอาร์เรย์ที่จัดเรียงหนึ่งรายการใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ที่จัดเรียงสองตัว arr1 และ arr2 ที่มีขนาด n และ n+1 โดยมีองค์ประกอบเหมือนกันทั้งหมด ยกเว้นองค์ประกอบพิเศษ งานของเราคือ ค้นหาดัชนีขององค์ประกอบพิเศษที่มีอยู่ในอาร์เรย์ที่จัดเรียงหนึ่งรายการ .

คำอธิบายปัญหา: เราจำเป็นต้องค้นหาดัชนีขององค์ประกอบจากอาร์เรย์ขนาด n+1 ซึ่งไม่มีอยู่ในอาร์เรย์ขนาด n

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล: arr1[n] ={3, 5, 7, 8, 9, 12}
arr2[n+1] ={3, 4, 5, 7, 8, 9, 12}

ผลลัพธ์: 1

คำอธิบาย:

องค์ประกอบที่มีค่า 4 เกินมาซึ่งอยู่ที่ดัชนี 1

แนวทางการแก้ปัญหา -

วิธีแก้ปัญหาง่ายๆ คือการใช้การจัดเรียงอาร์เรย์ทั้งสอง และด้วยองค์ประกอบเดียวที่ไม่เท่ากัน เราสามารถดำเนินการค้นหาเชิงเส้นและค้นหาองค์ประกอบใน arr2 ที่ไม่มีอยู่ใน arr1[]

อัลกอริทึม:

ขั้นตอนที่ 1: วนซ้ำสำหรับ i -> 0 ถึง n+1,

ขั้นตอนที่ 1.1: ค้นหาองค์ประกอบแปลก ๆ ถ้า arr1[i] !=arr2[i] ให้วงแตก

ขั้นตอนที่ 2: ส่งคืนค่า i.

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {
   
   int i;
   for (i = 0; i < n; i++)
      if (arr1[i] != arr2[i])
         break;
   return i;
}

int main()
{
   int arr1[] = {3, 5, 7, 8, 9, 12};
   int arr2[] = {3, 4, 5, 7, 8, 9, 12};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int extraIndex = findExtraElement(arr1, arr2, n);
   cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
   return 0;
}

ผลลัพธ์

The extra element is at index (1) and the value is 4

การแก้ปัญหานี้สามารถทำได้ดีขึ้นโดยใช้เทคนิคการค้นหาที่มีประสิทธิภาพมากขึ้น ซึ่งก็คือ binary search แทนที่จะลดระยะเวลาในการคำนวณของอัลกอริธึมเชิงเส้น:

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {
   
   int extraIndex = n;
   int start = 0, end = n - 1;
   while (start <= end)
   {
      int mid = (start + end) / 2;
      if (arr2[mid] == arr1[mid])
         start = mid + 1;
      else
      {
         extraIndex = mid;
         end = mid - 1;
      }
   }
   return extraIndex;
}

int main()
{
   int arr1[] = {3, 5, 7, 8, 9, 12};
   int arr2[] = {3, 4, 5, 7, 8, 9, 12};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int extraIndex = findExtraElement(arr1, arr2, n);
   cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
   return 0;
}

ผลลัพธ์

The extra element is at index (1) and the value is 4

แนวทางอื่น:

อีกวิธีหนึ่งในการแก้ปัญหาคือการค้นหาความแตกต่างที่แน่นอนระหว่างสองอาร์เรย์ซึ่งเป็นองค์ประกอบพิเศษ จากนั้นเราต้องหาดัชนีขององค์ประกอบพิเศษนี้ในอาร์เรย์ขนาด n+1 สามารถทำได้โดยใช้อัลกอริธึมการค้นหา

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;

int calcArraysum(int arr[], int n){
   int sum = 0;
   for(int i = 0; i < n; i++)
      sum += arr[i];
   return sum;
}

int findExtraElement(int arr1[], int arr2[], int n) {
   
   int extraValue = calcArraysum(arr2, n+1) - calcArraysum(arr1, n);

   for (int i = 0; i < n; i++)
   {
      if (arr2[i] == extraValue)
         return i;
   }
   return -1;
}

int main()
{
   int arr1[] = {3, 5, 7, 8, 9, 12};
   int arr2[] = {3, 4, 5, 7, 8, 9, 12};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int extraIndex = findExtraElement(arr1, arr2, n);
   cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
   return 0;
}

ผลลัพธ์

The extra element is at index (1) and the value is 4