数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中大小为k的窗口内第一个负整数
在这个问题中，我们得到一个包含N个整数值的数组arr[]和一个大小为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
解决这个问题的另一种方法是使用类似于**滑动窗口**的概念。为此，我们将为大小为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
更新于：2022年2月1日
920 次查看
广告