จำนวนเต็มลบตัวแรกในทุกหน้าต่างของขนาด k ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งประกอบด้วยค่าจำนวนเต็ม N และหน้าต่างขนาด N หน้าที่ของเราคือ สร้างโปรแกรมสำหรับค้นหาจำนวนเต็มลบตัวแรกในทุกหน้าต่างของขนาด 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 และในแต่ละหน้าต่างให้ค้นหาจำนวนเต็มลบแรกแล้วพิมพ์ออกมา

วิธีแก้ปัญหาคือวิธีไร้เดียงสาที่ใช้สองลูปซ้อนกันเพื่อดำเนินการ ดังนั้นความซับซ้อนของเวลาของการแก้ปัญหาจึงอยู่ในลำดับ 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

อีกวิธีในการแก้ปัญหาคือการใช้แนวคิดที่คล้ายกับหน้าต่างบานเลื่อน . สำหรับสิ่งนี้ เราจะสร้าง dequeue (คิวสองปลาย) ขนาด k สำหรับองค์ประกอบทั้งหมดของหน้าต่างขนาด k เราจะเริ่มสำรวจอาร์เรย์ตั้งแต่เริ่มต้นและเติมองค์ประกอบใน dequeue ของขนาด k จากนั้น สำหรับแต่ละองค์ประกอบของอาร์เรย์ เราจะลบองค์ประกอบหนึ่งออกจากส่วนท้ายและเพิ่มองค์ประกอบหนึ่งไปยังอีกองค์ประกอบหนึ่ง สำหรับแต่ละหน้าต่างที่เลื่อน เราจะค้นหาและพิมพ์ตัวเลขติดลบตัวแรก สำหรับการค้นหาจำนวนลบ เราจะตรวจสอบว่าตัวเลขที่ลบออกนั้นเป็นจำนวนลบตัวแรกของหน้าต่างหรือไม่ ถ้าใช่ เราจะตรวจสอบองค์ประกอบถัดไปสำหรับจำนวนลบตัวแรก มิฉะนั้นจะไม่ใช่

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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