이 문제에서는 크기가 n과 n+1인 두 개의 정렬된 배열 arr1과 arr2가 제공되며 추가 요소를 제외하고는 모든 요소가 동일합니다. 우리의 임무는 하나의 정렬된 배열에 있는 추가 요소의 인덱스를 찾는 것입니다. .
문제 설명: 크기가 n인 배열에 없는 n+1 크기의 배열에서 요소의 인덱스를 찾아야 합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력: arr1[n] ={3, 5, 7, 8, 9, 12}
arr2[n+1] ={3, 4, 5, 7, 8, 9, 12}
출력: 1
설명:
값이 4인 요소는 인덱스 1에 있는 추가 요소입니다.
해결 방법 -
문제에 대한 간단한 해결책은 두 배열이 모두 정렬된다는 사실을 사용하는 것입니다. 그리고 같지 않은 단 하나의 요소로 선형 검색을 수행하고 arr1[]에 없는 요소를 arr2에서 찾을 수 있습니다.
알고리즘:
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
이 솔루션은 이진 검색 과 같은 보다 효과적인 검색 기술을 사용하여 더 잘 만들 수 있습니다. 선형 대신 알고리즘의 계산 시간을 줄입니다.
우리 솔루션의 작동을 설명하는 프로그램,
예시
#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