配列に存在しない最初の「n」個の数値を見つけるPHPプログラム

配列の中に存在しない最初の「n」個の正の整数を求めるには、あらかじめ配列を昇順にソートしておき、1から順に値を照らし合わせていくのが基本的な考え方です。ここでは、そのアルゴリズムをPHPで実装した例を紹介します。

サンプルコード

<?php
   function missing_values($my_arr, $len, $n){
      sort($my_arr);
      $i = 0;
      while ($i < $n && $my_arr[$i] <= 0)
         $i++;
      $count = 0; $curr = 1;
      while ($count < $n && $i < $len){
         if ($my_arr[$i] != $curr){
            echo $curr , " ";
            $count++;
         }
         else
            $i++;
         $curr++;
      }
      while ($count < $n){
         echo $curr , " ";
         $curr++;
         $count++;
      }
   }
   $my_arr = array(6, 8, 0);
   $len = sizeof($my_arr);
   $n = 5;
   print_r("The missing values of the array are ");
   missing_values($my_arr, $len, $n);
?>

実行結果

The missing values of the array are 1 2 3 4 5

実行結果からわかるように、配列 {6, 8, 0} には 1〜5 の整数が含まれていないため、「1 2 3 4 5」が最初の5つの欠損値として出力されます。

コードの解説

まず、missing_values という名前の関数を定義しています。この関数は、対象となる配列、その長さ（$len）、そして取得したい欠損値の個数（$n）の3つの引数を受け取ります。

関数内では、最初に sort() 関数によって配列を昇順に並べ替えます。続いて変数 $i を 0 で初期化し、配列の先頭に含まれる 0 以下の値（ゼロや負の数）をスキップします。これは、探索対象を正の整数に限定するためです。

次に、$count を 0、$curr を 1 で初期化します。そして「$count が $n 未満、かつ $i が配列の長さ未満」という条件でループ処理を行います。ループ内では、現在注目している配列の要素 $my_arr[$i] と $curr を比較し、両者が一致しない場合は $curr が配列に存在しない値だと判断できるため、その値を出力して $count を1増やします。一致した場合は、配列側のポインタである $i を進めます。どちらの場合でも $curr は1ずつ増加していきます。

配列のすべての要素を走査し終えても $count が $n に達しない場合は、後続のwhileループによって、配列の最大値よりも先に位置する連続する整数を順番に出力していきます。これにより、配列の範囲外に連なる欠損値にも柔軟に対応できます。

関数の外側では、サンプル用の配列 array(6, 8, 0) を定義し、sizeof() 関数で要素数を取得して変数 $len に代入しています。ここでは $n = 5 としているため、「配列に存在しない最初の5つの数値」を求めることになります。最後に、これらの値を引数として関数を呼び出し、結果をコンソールに出力しています。

まとめ

このアルゴリズムは、ソート後に配列を一度だけ走査すればよいシンプルな構造で、負の値やゼロが混在する配列でも正しく動作します。「配列に含まれない小さい方からn個の整数を知りたい」というケースで、実務や学習の参考になる基本パターンといえるでしょう。