Tìm phần tử bị mất từ ​​một mảng trùng lặp trong C ++

Khái niệm

Đối với hai mảng đã cho là bản sao của nhau ngoại trừ một phần tử, điều đó có nghĩa là một phần tử từ một trong các mảng bị thiếu, nhiệm vụ của chúng tôi là xác định phần tử bị thiếu đó.

Đầu vào

arr1[] = {2, 5, 6, 8, 10}
arr2[] = {5, 6, 8, 10}

Đầu ra

2

2 bị thiếu trong mảng thứ hai.

Đầu vào

arr1[] = {3, 4, 5, 6}
arr2[] = {3, 4, 5, 6, 7}

Đầu ra

7

7 bị thiếu trong mảng đầu tiên.

Phương pháp

Ở đây, chúng tôi áp dụng một giải pháp đơn giản trong đó chúng tôi lặp lại các mảng và xác minh từng phần tử và đánh dấu phần tử bị thiếu khi phát hiện thấy một phần tử chưa khớp. Nhưng hạn chế của giải pháp này là nó yêu cầu thời gian tuyến tính theo kích thước của mảng.

Chúng tôi có thể triển khai một giải pháp hiệu quả khác dựa trên cách tiếp cận tìm kiếm nhị phân.Chúng tôi thực hiện theo thuật toán dưới đây được giải thích từng bước -

• Bắt đầu tìm kiếm nhị phân trong mảng lớn hơn và lấy giá trị trung bình là (thấp + cao) / 2
• Người ta đã thấy rằng nếu giá trị từ cả hai mảng giống nhau thì phần tử bị thiếu phải nằm trong phần bên phải để đánh dấu thấp là giữa
• Dấu khác cao đến giữa vì phần tử bị thiếu phải nằm ở phần bên trái của mảng lớn hơn nếu các phần tử ở giữa không giống nhau.
• Chúng tôi phải xử lý riêng trường hợp đặc biệt vì đối với phần tử đơn và mảng phần tử không, bản thân phần tử đơn lẻ sẽ là phần tử bị thiếu.

Người ta đã quan sát thấy rằng nếu bản thân phần tử đầu tiên không bằng nhau thì phần tử đó sẽ là phần tử bị thiếu.

Ví dụ

// C++ program to find missing element from same
// arrays (except one missing element)
#include <bits/stdc++.h>
using namespace std;
// Shows function to determine missing element based on binary
// search approach. arrA[] is of larger size and
// Q is size of it. arrA[] and arrB[] are assumed
// to be in same order.
int findMissingUtil(int arrA[], int arrB[], int Q){
   // Considers special case, for only element which is
   // missing in second array
   if (Q == 1)
      return arrA[0];
   // Considers special case, for first element missing
   if (arrA[0] != arrB[0])
      return arrA[0];
   // Used to initialize current corner points
   int low = 0, high = Q - 1;
   // Iterate until low < high
   while (low < high){
      int mid = (low + high) / 2;
      // It has been observed that if element at mid indices are equal
      // then go to right subarray
      if (arrA[mid] == arrB[mid])
         low = mid;
      else
         high = mid;
         // So if low, high becomes contiguous, break
      if (low == high - 1)
      break;
   }
   // Now missing element will be at high index of
   // bigger array
   return arrA[high];
}
// So this function mainly does basic error checking
// and calls findMissingUtil
void findMissing(int arrA[], int arrB[], int P, int Q){
   if (Q == P-1)
      cout << "Missing Element is "
      << findMissingUtil(arrA, arrB, P) << endl;
   else if (P == Q-1)
      cout << "Missing Element is "
      << findMissingUtil(arrB, arrA, Q) << endl;
   else
   cout << "Invalid Input";
}
// Driver Code
int main(){
   int arrA[] = {2, 5, 6, 8, 10};
   int arrB[] = {5, 6, 8, 10};
   int P = sizeof(arrA) / sizeof(int);
   int Q = sizeof(arrB) / sizeof(int);
   findMissing(arrA, arrB, P, Q);
   return 0;
}

Đầu ra

Missing Element is 2