C++のサイズkのすべてのウィンドウの最初の負の整数

この問題では、N個の整数値とサイズNのウィンドウで構成される配列arr []が与えられます。私たちのタスクは、サイズkのすべてのウィンドウで最初の負の整数を見つけるプログラムを作成することです。 。最初の負の数が存在する場合はそれを出力し、そうでない場合は0を出力し、負の数が存在しないことを示します。

問題を理解するために例を見てみましょう

Input: arr[] = {-2, 2, -1, 4, 3, -6}, k = 2
Output: -2, -1, -1, 0, -6

説明 −

Size of window k = 2,
{-2, 2}, first negative is -2
{2, -1}, first negative is -1
{-1, 4}, first negative is -1
{4, 3}, first negative is 0 (no negative exists)
{3, -6}, first negative is -6

ソリューションアプローチ

この問題を解決する簡単な方法は、配列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<<"First negative integer in each with of size "<<k<<" is \n";
   findFirstNegIntWindowK(arr, n, k);
   return 0;
}

出力

First negative integer in each with of size 2 is
-2 -1 -1 0 -6

この問題を解決するもう1つの方法は、スライディングウィンドウと同様の概念を使用することです。 。このために、デキューを作成します サイズkのウィンドウのすべての要素に対するサイズkの（両端キュー）。最初から配列のトラバースを開始し、サイズkのデキューに要素を入力します。次に、配列の要素ごとに、最後から1つの要素を削除し、1つの要素を別の要素に追加します。スライドしたウィンドウごとに、最初の負の数を見つけて印刷します。負の数を見つけるために、削除された数がウィンドウの最初の負の数であるかどうかを確認します。そうでない場合は、次の要素で最初の負の数を確認します。

例

ソリューションの動作を説明するプログラム

#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<<"First negative integer in each with of size "<<k<<" is \n";
   findFirstNegIntWindowK(arr, n, k);
   return 0;
}

出力

First negative integer in each with of size 2 is
-2 -1 -1 0 -6