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
-
配列から欠落している要素を見つけるためのPHPプログラム
「array_diff」関数を使用して、配列から欠落している要素を見つけることができます。 例 <?php function absent($my_list) { $my_array = range(min($my_list), max($my_list)); return array_diff($my_array, $my_list); } echo "Elements missing fr
-
Pythonで1からNまでの要素を含む配列で4つの欠落している数値を検索します
各数値が[1、N]の範囲にあり、配列サイズが(N-4)であり、単一の要素が繰り返されていない、個別の数値の配列があるとします。したがって、1からNまでの4つの数値が配列に欠落していることがわかります。これらの4つの欠落している番号を並べ替えて見つける必要があります。 したがって、入力がA =[2、8、4、13、6、11、9、5、10]の場合、出力は[1、3、7、12]になります。 これを解決するには、次の手順に従います- temp_arr:=すべて0のサイズ4の配列 0からAのサイズの範囲のiの場合、実行 temp:=| A [i] | temp <=Aのサイズの