C++で自然数から指定された整数を削除した後のK番目に小さい数を求める方法

このチュートリアルでは、自然数からいくつかの整数を削除した後に残る要素の中から、K番目に小さい数を見つけるプログラムを作成します。

問題の概要

整数の配列と値kが与えられます。自然数の列から、与えられた配列に含まれるすべての要素を取り除き、残った自然数の中でk番目に小さい数を求めるのが目的です。

例えば、配列が {3, 5}、k = 2 の場合、自然数は 1, 2, 4, 6, 7, ... となり、その中で2番目に小さい数は「2」になります。

解決手順

以下の手順で問題を解くことができます。

• 配列とkの値を初期化します。
• フラグ用の配列を用意し、与えられた配列に存在する要素以外をすべて0で初期化します。与えられた配列の要素には1を設定します。
• 自然数を先頭から順に走査するループを記述します。
  • 現在の値がフラグ配列でマークされていない場合、kをデクリメントします。
  • kが0になった時点で、その現在の値を返します。
• 該当する数が見つからない場合は0を返します。

実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int smallestNumber(int arr[], int n, int k) {
   int flag[MAX];
   memset(flag, 0, sizeof flag);
   for (int i = 0; i < n; i++) {
      flag[arr[i]] = 1;
   }
   for (int i = 1; i < MAX; i++) {
      if (flag[i] != 1) {
         k--;
      }
      if (!k) {
         return i;
      }
   }
   return 0;
}
int main() {
   int k = 2;
   int arr[] = { 3, 5 };
   cout << smallestNumber(arr, 2, k) << endl;
   return 0;
}

コードの解説

まず、memsetを使ってフラグ配列全体を0で初期化し、入力配列に含まれる値に対応するインデックスだけを1に設定します。その後、1から順に自然数を走査し、フラグが立っていない（＝削除されていない）数に出会うたびにkを減らしていきます。kが0になった瞬間の値が、求めるk番目に小さい数です。

このアルゴリズムの計算量はO(MAX + n)であり、MAXの値次第ではメモリ使用量が大きくなる点に注意が必要です。より効率的な方法としては、配列をソートして二分探索を組み合わせるアプローチもあります。

出力結果

上記のコードを実行すると、以下の結果が得られます。

2

まとめ

本チュートリアルでは、自然数から指定された整数を削除した後のk番目に小さい数を求める方法を学びました。フラグ配列を使ったシンプルなアプローチは理解しやすく、競技プログラミングなどでも応用できる基本的なテクニックです。チュートリアルについて質問がある場合は、コメント欄でお知らせください。