查找C ++中一个排序数组中存在的额外元素的索引
在这个问题中，我们给了两个大小分别为n和n+1的排序数组arr1和arr2，除多余元素外，所有元素都相同。我们的任务是找到存在于一个排序数组中的额外元素的索引。
问题描述： 我们需要从大小为n+1的数组中找到n+1大小的元素的索引。
让我们举个例子来了解这个问题，
输入： 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
通过使用更有效的搜索技术（二进制搜索 而不是线性减少算法的计算时间），可以更好地解决此问题：
该程序说明了我们解决方案的工作原理，
示例
#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