C++で連続番号のソートされた配列から欠落している要素を検索します

コンセプト

n個の異なる整数の特定の配列array[]に関して、要素は1つの欠落した要素とともに昇順で順番に配置されます。私たちの仕事は、不足している要素を特定することです。

入力

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