C++で1からNまでの要素を含む配列で4つの欠落している数値を検索します

コンセプト

与えられた配列の各整数が[1、N]の範囲にある一意の整数の与えられた配列に関して、配列のサイズは（N-4）であり、単一の要素は繰り返されません。したがって、1からNまでの4つの数値が配列にありません。欠落している4つの番号をソートされた順序で特定します。

入力

arr[] = {3, 6, 7, 4, 10}

出力

1 2 5 8 9

入力

arr[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 }

出力

1 3 7 12

メソッド

ここで、単純なO（N）ソリューションは、サイズNの補助配列を実装して、訪問した要素を示したりマークしたりすることです。入力配列にアクセスし、補助配列の要素を示すかマークします。最後に、示されていない、またはマークされていないすべてのインデックスを印刷します。

ここで、O（1）補助スペースを使用してどのように解決するかという疑問が生じます。

最初に、長さ4のhelperという名前の配列を初期化して、4つの欠落している数値を補正し、それらをゼロで埋めます。その後、givenarrayのi =0からi

• 要素の絶対値がinputarrayの長さよりも小さい場合は、array [temp]要素に-1を掛けます（訪問した要素を示したりマークしたりするため）。

• 要素の絶対値がinputarrayの長さよりも大きい場合、helper [temp％array.length]要素の値を-1に設定します（訪問した要素を示すまたはマークするため）。

ここで、入力配列と、値がまだゼロより大きいインデックスを繰り返し処理します。これらの要素は、入力配列で検出されませんでした。この結果、要素がゼロより大きいインデックスの（index + 1）値を出力します。

ここで、ヘルパー配列と、値がまだゼロより大きいインデックスを繰り返し処理します。これらの要素は、入力配列で検出されませんでした。この結果、要素がゼロより大きいインデックスの（index + array.length + 1）値を出力します。

例

// CPP program to find missing 4 elements
// in an array of size N where elements are
// in range from 1 to N+4.
#include <bits/stdc++.h>
using namespace std;
// Used to find missing 4 numbers in O(N) time
// and O(1) auxiliary space.
void missing4(int arr1[], int n1){
   // Used to keep track of 4 possible numbers
   // greater than length of input array
   // In case of Java, helper is automatically
   // initialized as 0.
   int helper[4];
   // Visit the input array and mark
   // visited elements either by marking
   // them as negative in arr[] or in
   // helper[].
   for (int i = 0; i < n1; i++) {
      int temp1 = abs(arr1[i]);
      // It has been seen that if element is smaller than or
      // equal to length, mark its
      // presence in arr1[]
      if (temp1 <= n1)
         arr1[temp1 - 1] *= (-1);
      // Indicate or mark presence in helper[]
      else if (temp1 > n1) {
         if (temp1 % n1 != 0)
            helper[temp1 % n1 - 1] = -1;
         else
            helper[(temp1 % n1) + n1 - 1] = -1;
      }
   }
   // Used to print all those elements whose presence
   // is not marked.
   for (int i = 0; i < n1; i++)
      if (arr1[i] > 0)
         cout << (i + 1) << " ";
   for (int i = 0; i < 4; i++)
      if (helper[i] >= 0)
         cout << (n1 + i + 1) << " ";
      return;
}
// Driver code
int main(){
   int arr1[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 };
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   missing4(arr1, n1);
   return 0;
}

出力

1 3 7 12