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

この記事では、サイズ n の配列 arr[] と、範囲を示す開始値・終了値が与えられたときに、範囲内で欠落している要素を見つける方法を解説します。

問題の概要

与えられた範囲 [start, end] に含まれるべき整数のうち、配列 arr[] に存在しない要素をすべて見つけて出力するのが目的です。

入力例

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

出力例

5, 8

説明

範囲は [3, 4, 5, 6, 7, 8] であり、配列は {4, 6, 3, 7} です。したがって、配列に存在しない範囲内の要素は 5 と 8 になります。

解決アプローチ

この問題は複数の方法で解くことができます。ここでは代表的な3つのアプローチを紹介します。

#アプローチ1: ソートと二分探索(lower_bound)を使う方法

最もシンプルな方法は、範囲の各要素が配列に存在するかを直接確認することです。まず配列をソートし、lower_bound を使って範囲の開始値に相当する位置を見つけます。その後、範囲の値と配列の要素を順に比較しながら、一致しない値(= 欠落している要素)を出力していきます。

実装例:

#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

この方法の計算量は、ソートに O(n log n)、比較処理に O(n + 範囲の長さ) となります。

#アプローチ2: ブール配列を使う方法

次の方法は、ブール配列を活用するアプローチです。サイズ (end − start + 1) のブール配列を作成し、配列 arr[] の各要素 v について、v が範囲内であれば boolArray[v − start] を true に設定します。最後にブール配列全体を走査し、false のままになっているインデックスに対応する値(start + i)を出力すれば、それが欠落している要素です。

実装例:

#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

この方法の計算量は O(n + 範囲の長さ) で、ソート不要のため高速に動作します。ただし、範囲が非常に大きい場合はメモリ消費に注意が必要です。

#アプローチ3: ハッシュテーブル(unordered_set)を使う方法

3つ目の方法は、ハッシュテーブルを利用するアプローチです。まず配列の全要素を unordered_set に挿入します。その後、範囲 [start, end] を順に走査し、セットに存在しない値を出力します。ハッシュセットによる検索は平均 O(1) で行えるため、効率的です。

実装例:

#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

まとめ

C++で範囲内の欠落要素を検索するには、主に以下の3つの方法があります。

• ソート + lower_bound: 追加メモリが少なくて済むが、ソートに O(n log n) かかる。
• ブール配列: 計算量 O(n + 範囲の長さ) で高速だが、範囲の大きさに応じたメモリが必要。
• unordered_set(ハッシュセット): 実装がシンプルで、平均 O(n + 範囲の長さ) の計算量。

データの規模や範囲の広さ、メモリ制約に応じて、最適なアプローチを選択しましょう。