查找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