C++で範囲の欠落している要素を検索する

この問題では、サイズnの配列arr []と、範囲を示すstart要素とend要素が与えられます。私たちの仕事は、範囲の欠落している要素を見つけることです。

問題の説明 −範囲内に存在しない範囲の要素を検索します。

問題を理解するために例を見てみましょう

入力

arr[] = {4, 6, 3, 7}, start = 3, end = 8

出力

5, 8

説明

範囲は[3、4、5、6、7、8]

配列は{4、6、3、7}

配列に存在しない範囲の要素は5、8

ソリューションアプローチ

この問題は複数の方法で解決できます。彼らは、

＃アプローチ1

簡単な解決策の1つは、配列内の範囲のすべての要素を直接チェックすることです。このために、配列を並べ替えてから、配列内の範囲の最初の要素を見つけてから、欠落している要素を見つけて出力します。

ソリューションの動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;
void findMissingElements(int arr[], int n, int low, int high){
   sort(arr, arr + n);
   int* pointerVal = lower_bound(arr, arr + n, low);
   int index = pointerVal - arr;
   int i = index, x = low;
   while (i < n && x <= high) {
      if (arr[i] != x)
         cout << x << " ";
      else
         i++;
         x++;
   }
   while (x <= high)
      cout<<x++<<" ";
}
int main(){
   int arr[] = { 4, 6, 3, 7 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int low = 3, high = 9;
   cout<<"The missing elements are ";
   findMissingElements(arr, n, low, high);
   return 0;
}

出力

The missing elements are 5 8 9

#Approach 2

この問題を解決する別のアプローチは、配列を使用することです。サイズのブール配列を作成します（end-start）。この配列の各要素について、（i + start）が配列に存在するかどうかを確認します。存在する場合は、arr [i] =trueとマークし、そうでない場合はarr [i]=falseとマークします。最後に、booleanArrayをトラバースし、falseとマークされたすべての要素を出力します。

ソリューションの動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;
void findMissingElements(int arr[], int n, int start, int end){
   bool boolArray[end - start + 1] = { false };
   for (int i = 0; i < n; i++) {
      if (start <= arr[i] && arr[i] <= end)
      boolArray[arr[i] - start] = true;
   }
   for (int i = 0; i <= end - start; i++) {
      if (boolArray[i] == false)
         cout<<(start + i)<<"\t";
   }
}
int main(){
   int arr[] = { 4, 6, 3, 7 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int low = 3, high = 9;
   cout<<"The missing elements are ";
   findMissingElements(arr, n, low, high);
   return 0;
}

出力

The missing elements are 5 8 9

＃アプローチ3

この問題を解決する別のアプローチは、ハッシュテーブルを使用することです。配列のすべての要素をハッシュテーブルに挿入し、挿入後に範囲をトラバースして、範囲内に存在しないすべての要素を出力します。

ソリューションの動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;
void findMissingElements(int arr[], int n, int start, int end){
   unordered_set<int> arrEle;
   for (int i = 0; i < n; i++)
      arrEle.insert(arr[i]);
   for (int i = start; i <= end; i++)
      if (arrEle.find(i) == arrEle.end())
         cout<<i<<"\t";
}
int main(){
   int arr[] = { 4, 6, 3, 7 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int low = 3, high = 9;
   cout<<"The missing elements are ";
   findMissingElements(arr, n, low, high);
   return 0;
}

出力

The missing elements are 5 8 9