C++でサイズkのすべてのウィンドウにおける最初の負の整数を求める方法

この問題では、N個の整数からなる配列 arr[] とサイズkのウィンドウが与えられます。求めるのは、サイズkの各ウィンドウに含まれる最初の負の整数を見つけるプログラムです。負の数が存在する場合はその値を出力し、存在しない場合は「0」を出力して負の数がないことを示します。

問題の例

具体的な入力と出力を見て、問題を理解しましょう。

入力：arr[] = {-2, 2, -1, 4, 3, -6}, k = 2
出力：-2, -1, -1, 0, -6

解説：

ウィンドウサイズ k = 2 の場合、
{-2, 2} → 最初の負の数は -2
{2, -1} → 最初の負の数は -1
{-1, 4} → 最初の負の数は -1
{4, 3} → 負の数は存在しないため 0
{3, -6} → 最初の負の数は -6

解法アプローチ1：単純な走査（ナイーブな方法）

最もシンプルな方法は、配列 arr[] を走査しながらサイズkのウィンドウを作成し、各ウィンドウ内で最初の負の整数を探して出力するものです。

この方法では2重ループを使用するため、時間計算量は O(n×k) となります。実装は容易ですが、大規模な配列には非効率です。

サンプルコード

#include <iostream>
using namespace std;

void findFirstNegIntWindowK(int arr[], int n, int k){
   bool negFound;
   for (int i = 0; i<(n-k+1); i++)
   {
      negFound = false;
      for (int j = 0; j<k; j++)
      {
         if (arr[i+j] < 0)
         {
            cout<<arr[i+j]<<"\t";
            negFound = true;
            break;
         }
      }
      if (!negFound)
         cout<<"0\t";
   }
}

int main(){
   int arr[] = {-2, 2, -1, 4, 3, -6};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 2;
   cout<<"サイズ "<<k<<" の各ウィンドウの最初の負の整数は \n";
   findFirstNegIntWindowK(arr, n, k);
   return 0;
}

出力結果

サイズ 2 の各ウィンドウの最初の負の整数は
-2 -1 -1 0 -6

解法アプローチ2：スライディングウィンドウ（両端キュー）を使った効率的な方法

より効率的な方法として、スライディングウィンドウの考え方を応用できます。この手法では、両端から要素の出し入れができる deque（両端キュー） を使用します。

まず配列を先頭から走査し、サイズkのウィンドウに含まれる要素をdequeに入れていきます。その後、配列を1つ進むごとに、dequeから末尾側の要素を1つ取り除き、新しい要素を追加します。ウィンドウがスライドするたびに、最初の負の数を探して出力します。

負の数を探す際のポイントは、「取り除かれた要素がそのウィンドウの最初の負の数かどうか」をチェックすることです。もし取り除かれた要素が最初の負の数だった場合は、次の候補を確認します。そうでなければ、dequeの先頭にあるインデックスが指す要素がそのまま答えになります。この方法により、時間計算量を O(n) まで改善できます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

void findFirstNegIntWindowK(int arr[], int n, int k){
   deque<int> windowKsize;
   int i = 0;
   // 最初のウィンドウに含まれる負の数のインデックスを記録
   for (; i < k; i++)
      if (arr[i] < 0)
         windowKsize.push_back(i);
   // ウィンドウをスライドさせながら処理
   for (; i < n; i++){
      if (!windowKsize.empty())
         cout<<arr[windowKsize.front()]<<"\t";
      else
         cout<<"0\t";
      // ウィンドウ外に出たインデックスを削除
      while ( (!windowKsize.empty()) && windowKsize.front() < (i - k + 1))
         windowKsize.pop_front();
      // 現在の要素が負ならインデックスを追加
      if (arr[i] < 0)
         windowKsize.push_back(i);
   }
   // 最後のウィンドウの結果を出力
   if (!windowKsize.empty())
      cout<<arr[windowKsize.front()]<<" \t";
   else
      cout<<"0\t";
}

int main(){
   int arr[] = {-2, 2, -1, 4, 3, -6};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 2;
   cout<<"サイズ "<<k<<" の各ウィンドウの最初の負の整数は \n";
   findFirstNegIntWindowK(arr, n, k);
   return 0;
}

出力結果

サイズ 2 の各ウィンドウの最初の負の整数は
-2 -1 -1 0 -6

まとめ

サイズkの各ウィンドウにおける最初の負の整数を求める問題には、2つのアプローチがあります。単純な2重ループによる方法は O(n×k)、dequeを活用したスライディングウィンドウ法は O(n) と、後者が大幅に効率的です。データ量が多い場合は、スライディングウィンドウ法を採用することをおすすめします。