在C ++中的连续数字排序数组中查找丢失的元素

概念

对于n个不同整数的给定array 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;
//显示函数以返回缺少的元素
int findMissing(int array[], int n1){
   int low = 0, high = n1 - 1;
   int mid1;
   while (high > low){
      mid1 = low + (high - low) / 2;
      //验证中间元素是否一致
      if (array[mid1] - mid1 == array[0]){
         //在这里，直到中间元素没有矛盾
         //当缺少元素在
         //中间元素
         if (array[mid1 + 1] - array[mid1] > 1)
            return array[mid1] + 1;
         else{
            //往右走
            low = mid1 + 1;
         }
      }
      else{
         //在这里发现不一致
         //当缺少元素在之前
         //中间元素
         if (array[mid1] - array[mid1 - 1] > 1)
            return array[mid1] - 1;
         else{
            //向左走
            high = mid1 - 1;
         }
      }
   }
   //在这里，找不到丢失的元素
   return -1;
}
//驱动程式码
int main(){
   int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };
   int n1 = sizeof(array)/sizeof(array[0]);
   cout <<"缺少的元素：" <<(findMissing(array, n1));
}

输出结果

缺少的元素：-7