Số nguyên âm đầu tiên trong mọi cửa sổ có kích thước k trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm N giá trị nguyên và một cửa sổ có kích thước N. Nhiệm vụ của chúng ta là tạo một chương trình để tìm số nguyên âm đầu tiên trong mọi cửa sổ có kích thước k . Chúng tôi sẽ in số âm đầu tiên nếu nó tồn tại, nếu không thì in 0, biểu thị không tồn tại số âm.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Giải thích -

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

Phương pháp tiếp cận giải pháp

Một phương pháp đơn giản để giải quyết vấn đề là bằng cách duyệt qua mảng arr [] tạo các cửa sổ có kích thước k. Và trong mỗi cửa sổ, tìm số nguyên âm đầu tiên và in nó.

Giải pháp là một giải pháp ngây thơ sử dụng hai vòng lặp lồng nhau để thực hiện hoạt động. Do đó, độ phức tạp về thời gian của giải pháp là bậc O (n * k).

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

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

Một phương pháp khác để giải quyết vấn đề là sử dụng một khái niệm tương tự như cửa sổ trượt . Đối với điều này, chúng tôi sẽ tạo một dequeue (hàng đợi kết thúc kép) có kích thước k cho tất cả các phần tử của cửa sổ có kích thước k. Chúng tôi sẽ bắt đầu duyệt qua mảng từ đầu và điền phần tử vào hàng có kích thước k. Và sau đó, đối với mỗi phần tử của mảng, chúng ta sẽ xóa một phần tử ở cuối và thêm phần tử này vào phần tử khác. Đối với mỗi cửa sổ trượt, chúng tôi sẽ tìm và in số âm đầu tiên. Để tìm số âm, chúng tôi sẽ kiểm tra xem số bị loại bỏ có phải là số âm đầu tiên của cửa sổ hay không, nếu có chúng tôi sẽ kiểm tra các phần tử tiếp theo xem có số âm đầu tiên hay không.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

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