컨셉
하나의 요소를 제외하고 서로 중복되는 주어진 두 개의 배열과 관련하여, 이는 배열 중 하나에서 하나의 요소가 누락되었음을 의미하며, 해당 누락된 요소를 판별하는 것이 우리의 임무입니다.
입력
arr1[] = {2, 5, 6, 8, 10}
arr2[] = {5, 6, 8, 10} 출력
2
두 번째 배열에서 2가 누락되었습니다.
입력
arr1[] = {3, 4, 5, 6}
arr2[] = {3, 4, 5, 6, 7} 출력
7
첫 번째 배열에서 7이 누락되었습니다.
방법
여기에서 배열을 반복하고 요소별로 확인하고 일치하지 않는 항목이 감지되면 누락된 요소를 표시하는 간단한 솔루션을 적용합니다. 그러나 이 솔루션의 단점은 배열 크기에 대해 선형 시간이 필요하다는 것입니다.
우리는 이진 검색 접근 방식을 기반으로 하는 또 다른 효율적인 솔루션을 구현할 수 있습니다. 우리는 단계별로 설명되는 아래 알고리즘을 따릅니다 -
- 더 큰 배열에서 이진 검색을 시작하고 중간을 (낮음 + 높음) / 2로 가져옵니다.
- 두 배열의 값이 같으면 누락된 요소가 오른쪽 부분에 있어야 하므로 low를 mid로 표시
- 중간 요소가 동일하지 않은 경우 누락된 요소가 더 큰 배열의 왼쪽 부분에 있어야 하므로 그렇지 않으면 high를 mid로 표시합니다.
- 단일 요소와 0개의 요소 배열의 경우 단일 요소 자체가 누락된 요소가 되므로 특수한 경우를 별도로 처리해야 합니다.
첫 번째 요소 자체가 같지 않으면 해당 요소가 누락된 요소가 되는 것으로 관찰되었습니다.
예시
// 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;
} 출력
Missing Element is 2