C++ 中每个大小为 k 的窗口中的第一个负整数
c++server side programmingprogramming更新于 2025/5/31 8:52:17
在此问题中，我们给出了一个由 N 个整数值组成的数组 arr[] 和一个大小为 N 的窗口。我们的任务是创建一个程序来查找每个大小为 k 的窗口中的第一个负整数。如果存在第一个负数，我们将打印它，否则打印 0，表示不存在负数。
让我们举一个例子来理解这个问题，
输入:arr[] = {-2, 2, -1, 4, 3, -6}, k = 2
输出:-2, -1, -1, 0, -6
解释 −
Size of window k = 2,
{-2, 2}，第一个负数为 -2
{2, -1}，第一个负数为 -1
{-1, 4}，第一个负数为 -1
{4, 3}，第一个负数为 0(不存在负数)
{3, -6}，第一个负数为 -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
另一种解决问题的方法是使用类似于滑动窗口的概念。为此，我们将为大小为 k 的窗口的所有元素创建一个大小为 k 的出队(双端队列)。我们将从开始处开始遍历数组，并将元素填充到大小为 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
