資料結構
網路
關係資料庫管理系統(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 次檢視
廣告