컨셉
n개의 고유한 정수로 구성된 주어진 배열 array[]와 관련하여 요소는 하나의 누락된 요소와 함께 오름차순으로 순차적으로 배치됩니다. 우리의 임무는 누락된 요소를 확인하는 것입니다.
입력
array[] = {1, 2, 3, 4, 5, 6, 7, 9} 출력
8
입력
array[] = {-4, -2, -1, 0, 1, 2} 출력
-3
입력
array[] = {1, 2, 3, 4} 출력
-1
누락된 요소가 없습니다.
방법
원칙
-
불일치 찾기:이 원칙에 따르면 모든 요소와 해당 인덱스의 차이는 모든 요소에 대해 array[0]이어야 합니다.
예
A[] ={1, 2, 3, 4, 5} -> 일관성
B[] ={201, 202, 203, 204} -> 일관성
C[] ={1, 2, 3, 5, 6} -> C[3]과 일치하지 않음 – 3 !=C[0] 즉 5 – 3 !=1
-
불일치를 결정하면 O(logN)에서 매번 어레이의 절반만 스캔하는 데 도움이 됩니다.
알고리즘
-
중간 요소를 결정하고 일관성이 있는지 확인합니다.
-
중간 요소가 일치하면 중간 요소와 다음 요소의 차이가 1보다 큰지 확인합니다. 즉, array[mid + 1] – array[mid]> 1
인지 확인합니다.-
그렇다면 array[mid] + 1이 누락된 요소입니다.
-
그렇지 않으면 중간 요소에서 오른쪽 절반 배열을 스캔하고 1단계로 이동해야 합니다.
-
-
중간 요소가 일치하지 않으면 중간 요소와 이전 요소 간의 차이가 1보다 큰지 확인합니다. 즉, array[mid] – array[mid – 1]> 1
인지 확인합니다.-
그렇다면 array[mid] – 1이 누락된 요소입니다.
-
그렇지 않으면 중간 요소에서 왼쪽 절반 배열을 스캔하고 1단계로 이동해야 합니다.
-
예시
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Shows function to return the missing element
int findMissing(int array[], int n1){
int low = 0, high = n1 - 1;
int mid1;
while (high > low){
mid1 = low + (high - low) / 2;
// Verify if middle element is consistent
if (array[mid1] - mid1 == array[0]){
// Here, no inconsistency till middle elements
// When missing element is just after
// the middle element
if (array[mid1 + 1] - array[mid1] > 1)
return array[mid1] + 1;
else{
// Go right
low = mid1 + 1;
}
}
else{
// Here inconsistency found
// When missing element is just before
// the middle element
if (array[mid1] - array[mid1 - 1] > 1)
return array[mid1] - 1;
else{
// Go left
high = mid1 - 1;
}
}
}
// Here, no missing element found
return -1;
}
// Driver code
int main(){
int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };
int n1 = sizeof(array)/sizeof(array[0]);
cout <<"The Missing Element:" <<(findMissing(array, n1));
} 출력
The Missing Element:-7