【C++】配列内のすべての「1」が少なくともK個以上離れているかどうかを判定する方法

問題概要

0と1のみで構成される配列 nums と整数 k が与えられたとします。このとき、配列内のすべての「1」が互いに少なくとも k 個以上離れて配置されているかどうかを判定し、条件を満たしていれば true を、そうでなければ false を返すプログラムを作成します。

例えば、入力が nums = [1,0,0,0,1,0,0,1]、k = 2 の場合、出力は true になります。これは、それぞれの「1」が互いに2つ以上の間隔をあけて配置されているためです。

解法のアプローチ

この問題は、配列を先頭から一度だけ走査する線形探索（O(n)）で効率的に解くことができます。ポイントは、「直前に現れた1の位置」を記録しておき、新しい「1」を見つけるたびに間隔をチェックすることです。

具体的な手順は以下の通りです。

• 変数 last を -1 で初期化します（まだ「1」が見つかっていないことを示す）。この変数には、直前に見つけた「1」のインデックスを格納します。

• i を 0 から配列のサイズまで 1 ずつ増加させながら、以下の処理を繰り返します。

  • nums[i] が 1 の場合：

    • last == -1（最初の「1」である）、または (i - last - 1) >= k（前の「1」との間隔が k 以上である）を満たせば、last := i と更新します。

    • それ以外の場合は、条件を満たしていないため、即座に false を返します。

• ループを最後まで抜けられた場合は、すべての「1」が条件を満たしているので true を返します。

C++による実装例

それでは、上記の手順を実際のコードで確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool kLengthApart(vector<int>& nums, int k) {
      int last = -1;
      for (int i = 0; i < nums.size(); i++) {
         if (nums[i] == 1) {
            if (last == -1 || (i - last - 1) >= k)
               last = i;
            else
               return false;
         }
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,0,0,0,1,0,0,1};
   cout << (ob.kLengthApart(v, 2));
}

入力

{1,0,0,0,1,0,0,1}

出力

1

出力が 1（true）となっており、すべての「1」が互いに少なくとも2つ以上離れていることが正しく判定できています。

計算量の分析

• 時間計算量： O(n) ― 配列を一度だけ走査するため、要素数 n に比例した時間で処理が完了します。

• 空間計算量： O(1) ― 追加のデータ構造を使用せず、変数 last だけで済むため、定数のメモリしか消費しません。

まとめ

本記事では、配列内のすべての「1」が少なくとも k 個以上離れているかどうかを判定するアルゴリズムを紹介しました。直前に見つけた「1」のインデックスを1つの変数で管理するだけで、追加メモリ不要・線形時間という非常にシンプルかつ効率的な解法になります。配列の走査系の基本的なパターンの一つとして、ぜひマスターしておきましょう。