C++でソート済み配列の欠落範囲（Missing Ranges）を検出する方法

問題の概要

ソート済みの整数配列 nums が与えられ、その要素は閉区間 [lower, upper] の範囲内に収まっているものとします。このとき、指定された範囲の中で配列に含まれていない「欠落している範囲」をすべて求めるのが本問題です。

たとえば、nums = [0, 1, 3, 50, 75]、lower = 0、upper = 99 という入力が与えられた場合、出力は ["2", "4->49", "51->74", "76->99"] となります。

解法のアプローチ

この問題は、範囲の下限から上限へと順番に走査しながら、配列の要素と突き合わせていくことで解けます。具体的な手順は以下の通りです。

• まず、重複を取り除いた配列 nums を用意します。元の配列 t を走査し、セット v に未登録の要素だけを nums の末尾に追加していきます。
• 結果を格納するための配列 ret を定義します。
• 現在注目している値 curr を lower で初期化し、インデックス i = 0、配列長 n を設定します。
• curr が upper 以下である限り、次の処理を繰り返します。
  • nums[i] が curr と一致する場合は値が連続していることを意味するため、i と curr をそれぞれ1つ進めます。
  • 一致しない場合はそこで欠落が発生しています。curr を文字列化して temp に保存し、curr を1つ進めます。
  • 次の要素 nums[i] が進めた後の curr と一致するなら、欠落は単一の値なので temp をそのまま結果に追加して次の反復へ進みます。
  • それ以外の場合は範囲として表現します。すでに配列の末尾に達している（i == n）なら、"->" と upper を連結して最後の欠落範囲を作成し、curr を upper + 1 にしてループを抜けられるようにします。まだ要素が残っているなら、"->" と nums[i] - 1 を連結した上で、curr を nums[i] までジャンプさせます。
• ループ終了後、ret を返します。

C++による実装例

より理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<string> findMissingRanges(vector<int>& t, int lower, int upper) {
       vector <int> nums;
       set <long long int> v;
       for(int i = 0; i < t.size(); i++){
          if(!v.count(t[i])){
             v.insert(t[i]);
             nums.push_back(t[i]);
          }
       }
       vector < string > ret;
       long long int curr = lower;
       int i = 0;
       int n = nums.size();
       while(curr <= upper){
          if(i < n && nums[i] == curr){
             i++;
             curr++;
          }
          else{
             string temp = to_string(curr);
             curr++;
             if(i < n && nums[i] == curr){
                ret.push_back(temp);
                continue;
             }
             else{
                if(i == n){
                   if(curr <= upper){
                      temp += "->";
                      temp += to_string(upper);
                      curr = (long long int )upper + 1;
                   }
                   ret.push_back(temp);
                }
                else{
                   temp += "->";
                   curr = nums[i];
                   temp += to_string(curr - 1);
                   curr = nums[i];
                   ret.push_back(temp);
                }
             }
          }
       }
       return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {0,1,3,50,75};
    print_vector(ob.findMissingRanges(v, 0, 99));
}

入力例

{0,1,3,50,75}, 0, 99

出力例

[2, 4->49, 51->74, 76->99]

計算量と実装上のポイント

このアルゴリズムは配列を一度走査するだけで完結するため、時間計算量は O(n) です。補助的に使うセットや結果配列も入力サイズに比例する程度に収まるため、空間計算量も O(n) となります。

また、curr を long long int として扱っている点にも注目してください。lower や upper が int 型の最大値・最小値付近にある場合、curr = upper + 1 のような演算でオーバーフローが発生する恐れがありますが、より大きな型を使うことで安全に処理できます。単一の欠落値と連続的な欠落範囲を "->" の有無で使い分けて文字列を組み立てる部分が、この実装の核心といえるでしょう。