Dado un arreglo y un entero positivo k, encuentre el primer entero negativo para cada ventana (subarreglo contiguo) de tamaño k. Si una ventana no contiene un entero negativo, imprima 0 para esa ventana.
Ejemplos:
Input : arr[] = {-8, 2, 3, -6, 10}, k = 2
Output : -8 0 -6 -6
First negative integer for each window of size k
{-8, 2} = -8
{2, 3} = 0 (does not contain a negative integer)
{3, -6} = -6
{-6, 10} = -6
Input : arr[] = {12, -1, -7, 8, -15, 30, 16, 28} , k = 3
Output : -1 -1 -7 -15 -15 0
Ejecute dos bucles. En el bucle exterior, tome todos los subarreglos (ventanas) de tamaño k. En el ciclo interno, obtenga el primer entero negativo del subarreglo actual (ventana).
C++
// C++ implementation to find the first negative
// integer in every window of size k
#include <bits/stdc++.h>
using namespace std;
// function to find the first negative
// integer in every window of size k
void printFirstNegativeInteger(int arr[], int n, int k)
{
// flag to check whether window contains
// a negative integer or not
bool flag;
// Loop for each subarray(window) of size k
for (int i = 0; i<(n-k+1); i++)
{
flag = false;
// traverse through the current window
for (int j = 0; j<k; j++)
{
// if a negative integer is found, then
// it is the first negative integer for
// current window. Print it, set the flag
// and break
if (arr[i+j] < 0)
{
cout << arr[i+j] << " ";
flag = true;
break;
}
}
// if the current window does not
// contain a negative integer
if (!flag)
cout << "0" << " ";
}
}
// Driver program to test above functions
int main()
{
int arr[] = {12, -1, -7, 8, -15, 30, 16, 28};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
printFirstNegativeInteger(arr, n, k);
return 0;
}
Java
// Java implementation to find the first negative
// integer in every window of size k
import java.util.*;
class solution
{
// function to find the first negative
// integer in every window of size k
static void printFirstNegativeInteger(int arr[], int n, int k)
{
// flag to check whether window contains
// a negative integer or not
boolean flag;
// Loop for each subarray(window) of size k
for (int i = 0; i<(n-k+1); i++)
{
flag = false;
// traverse through the current window
for (int j = 0; j<k; j++)
{
// if a negative integer is found, then
// it is the first negative integer for
// current window. Print it, set the flag
// and break
if (arr[i+j] < 0)
{
System.out.print((arr[i+j])+" ");
flag = true;
break;
}
}
// if the current window does not
// contain a negative integer
if (!flag)
System.out.print("0"+" ");
}
}
// Driver program to test above functions
public static void main(String args[])
{
int arr[] = {12, -1, -7, 8, -15, 30, 16, 28};
int n = arr.length;
int k = 3;
printFirstNegativeInteger(arr, n, k);
}
}
// This code is contributed by
// Shashank_Sharma
Python3
# Python3 implementation to find the first negative
# integer in every window of size k
# Function to find the first negative
# integer in every window of size k
def printFirstNegativeInteger(arr, n, k):
# Loop for each subarray(window) of size k
for i in range(0, (n - k + 1)):
flag = False
# Traverse through the current window
for j in range(0, k):
# If a negative integer is found, then
# it is the first negative integer for
# current window. Print it, set the flag
# and break
if (arr[i + j] < 0):
print(arr[i + j], end = " ")
flag = True
break
# If the current window does not
# contain a negative integer
if (not(flag)):
print("0", end = " ")
# Driver Code
arr = [12, -1, -7, 8, -15, 30, 16, 28]
n = len(arr)
k = 3
printFirstNegativeInteger(arr, n, k)
# This code is contributed by 'Smitha dinesh semwal'
C#
// C# implementation to find
// the first negative integer
// in every window of size k
using System;
class GFG
{
// function to find the first negative
// integer in every window of size k
static void printFirstNegativeInteger(int []arr,
int n, int k)
{
// flag to check whether window contains
// a negative integer or not
bool flag;
// Loop for each subarray(window) of size k
for (int i = 0; i < (n - k + 1); i++)
{
flag = false;
// traverse through the current window
for (int j = 0; j < k; j++)
{
// if a negative integer is found, then
// it is the first negative integer for
// current window. Print it, set the flag
// and break
if (arr[i + j] < 0)
{
Console.Write((arr[i + j]) + " ");
flag = true;
break;
}
}
// if the current window does not
// contain a negative integer
if (!flag)
Console.Write("0" + " ");
}
}
// Driver code
public static void Main(String []args)
{
int []arr = {12, -1, -7, 8, -15, 30, 16, 28};
int n = arr.Length;
int k = 3;
printFirstNegativeInteger(arr, n, k);
}
}
// This code has been contributed
// by 29AjayKumar
Javascript
<script>
// JavaScript implementation to find
// the first negative integer
// in every window of size k
function printFirstNegativeInteger(arr, n, k)
{
// flag to check whether window contains
// a negative integer or not
let flag;
// Loop for each subarray(window) of size k
for (let i = 0; i<(n-k+1); i++)
{
flag = false;
// traverse through the current window
for (let j = 0; j<k; j++)
{
// if a negative integer is found, then
// it is the first negative integer for
// current window. Print it, set the flag
// and break
if (arr[i+j] < 0)
{
document.write((arr[i+j])+" ");
flag = true;
break;
}
}
// if the current window does not
// contain a negative integer
if (!flag)
document.write("0"+" ");
}
}
// Driver Code
let arr = [12, -1, -7, 8, -15, 30, 16, 28];
let n = arr.length;
let k = 3;
printFirstNegativeInteger(arr, n, k);
// This code is contributed by avijitmondal1998.
</script>
Producción
-1 -1 -7 -15 -15 0
Complejidad de tiempo: el ciclo externo se ejecuta n-k+1 veces y el ciclo interno se ejecuta k veces para cada iteración del ciclo externo. Entonces, la complejidad del tiempo es O((n-k+1)*k) que también se puede escribir como O(nk) cuando k es comparativamente mucho más pequeño que n; de lo contrario, cuando k tiende a alcanzar n, la complejidad se convierte en O(k).
Enfoque 2: Enfoque eficiente
Creamos un Dequeue, Di de capacidad k, que almacena solo elementos útiles de la ventana actual de k elementos. Un elemento es útil si está en la ventana actual y es un entero negativo. Procesamos todos los elementos de la array uno por uno y mantenemos Di para que contenga elementos útiles de la ventana actual y estos elementos útiles son todos números enteros negativos. Para una ventana en particular, si Di no está vacío, entonces el elemento al frente de Di es el primer entero negativo para esa ventana; de lo contrario, esa ventana no contiene un entero negativo.
Es una variación del problema de Sliding Window Maximum .
Implementación:
C++
// C++ implementation to find the first negative
// integer in every window of size k
#include <bits/stdc++.h>
using namespace std;
// function to find the first negative
// integer in every window of size k
void printFirstNegativeInteger(int arr[], int n, int k)
{
// A Double Ended Queue, Di that will store indexes of
// useful array elements for the current window of size k.
// The useful elements are all negative integers.
deque<int> Di;
/* Process first k (or first window) elements of array */
int i;
for (i = 0; i < k; i++)
// Add current element at the rear of Di
// if it is a negative integer
if (arr[i] < 0)
Di.push_back(i);
// Process rest of the elements, i.e., from arr[k] to arr[n-1]
for ( ; i < n; i++)
{
// if Di is not empty then the element at the
// front of the queue is the first negative integer
// of the previous window
if (!Di.empty())
cout << arr[Di.front()] << " ";
// else the window does not have a
// negative integer
else
cout << "0" << " ";
// Remove the elements which are out of this window
while ( (!Di.empty()) && Di.front() < (i - k + 1))
Di.pop_front(); // Remove from front of queue
// Add current element at the rear of Di
// if it is a negative integer
if (arr[i] < 0)
Di.push_back(i);
}
// Print the first negative
// integer of last window
if (!Di.empty())
cout << arr[Di.front()] << " ";
else
cout << "0" << " ";
}
// Driver program to test above functions
int main()
{
int arr[] = {12, -1, -7, 8, -15, 30, 16, 28};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
printFirstNegativeInteger(arr, n, k);
return 0;
}
Java
// Java implementation to find the
// first negative integer in
// every window of size k
import java.util.*;
class GFG
{
// function to find the first negative
// integer in every window of size k
static void printFirstNegativeInteger(int arr[],
int n, int k)
{
// A Double Ended Queue, Di that will
// store indexes of useful array elements
// for the current window of size k.
// The useful elements are all negative integers.
LinkedList<Integer> Di = new LinkedList<>();
// Process first k (or first window)
// elements of array
int i;
for (i = 0; i < k; i++)
// Add current element at the rear of Di
// if it is a negative integer
if (arr[i] < 0)
Di.add(i);
// Process rest of the elements,
// i.e., from arr[k] to arr[n-1]
for ( ; i < n; i++)
{
// if Di is not empty then the element
// at the front of the queue is the first
// negative integer of the previous window
if (!Di.isEmpty())
System.out.print(arr[Di.peek()] + " ");
// else the window does not have a
// negative integer
else
System.out.print("0" + " ");
// Remove the elements which are
// out of this window
while ((!Di.isEmpty()) &&
Di.peek() < (i - k + 1))
Di.remove(); // Remove from front of queue
// Add current element at the rear of Di
// if it is a negative integer
if (arr[i] < 0)
Di.add(i);
}
// Print the first negative
// integer of last window
if (!Di.isEmpty())
System.out.print(arr[Di.peek()] + " ");
else
System.out.print("0" + " ");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {12, -1, -7, 8, -15, 30, 16, 28};
int n = arr.length;
int k = 3;
printFirstNegativeInteger(arr, n, k);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation to find the # first negative integer in every window # of size k import deque() from collections from collections import deque # function to find the first negative # integer in every window of size k def printFirstNegativeInteger(arr, n, k): # A Double Ended Queue, Di that will store # indexes of useful array elements for the # current window of size k. The useful # elements are all negative integers. Di = deque() # Process first k (or first window) # elements of array for i in range(k): # Add current element at the rear of Di # if it is a negative integer if (arr[i] < 0): Di.append(i); # Process rest of the elements, i.e., # from arr[k] to arr[n-1] for i in range(k, n): # if the window does not have # a negative integer if (not Di): print(0, end = ' ') # if Di is not empty then the element # at the front of the queue is the first # negative integer of the previous window else: print(arr[Di[0]], end = ' '); # Remove the elements which are # out of this window while Di and Di[0] <= (i - k): Di.popleft() # Remove from front of queue # Add current element at the rear of Di # if it is a negative integer if (arr[i] < 0): Di.append(i); # Print the first negative # integer of last window if not Di: print(0) else: print(arr[Di[0]], end = " ") # Driver Code if __name__ =="__main__": arr = [12, -1, -7, 8, -15, 30, 16, 28] n = len(arr) k = 3 printFirstNegativeInteger(arr, n, k); # This code is contributed by # chaudhary_19 (Mayank Chaudhary)
C#
// C# implementation to find the
// first negative integer in
// every window of size k
using System;
using System.Collections.Generic;
class GFG
{
// function to find the first negative
// integer in every window of size k
static void printFirstNegativeint(int []arr,
int n, int k)
{
// A Double Ended Queue, Di that will
// store indexes of useful array elements
// for the current window of size k.
// The useful elements are all
// negative integers.
List<int> Di = new List<int>();
// Process first k (or first window)
// elements of array
int i;
for (i = 0; i < k; i++)
// Add current element at the rear of Di
// if it is a negative integer
if (arr[i] < 0)
Di.Add(i);
// Process rest of the elements,
// i.e., from arr[k] to arr[n-1]
for ( ; i < n; i++)
{
// if Di is not empty then the element
// at the front of the queue is the first
// negative integer of the previous window
if (Di.Count != 0)
Console.Write(arr[Di[0]] + " ");
// else the window does not have a
// negative integer
else
Console.Write("0" + " ");
// Remove the elements which are
// out of this window
while ((Di.Count != 0) &&
Di[0] < (i - k + 1))
// Remove from front of queue
Di.RemoveAt(0);
// Add current element at the rear of Di
// if it is a negative integer
if (arr[i] < 0)
Di.Add(i);
}
// Print the first negative
// integer of last window
if (Di.Count!=0)
Console.Write(arr[Di[0]] + " ");
else
Console.Write("0" + " ");
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {12, -1, -7, 8, -15, 30, 16, 28};
int n = arr.Length;
int k = 3;
printFirstNegativeint(arr, n, k);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript implementation to find the
// first negative integer in
// every window of size k
// function to find the first negative
// integer in every window of size k
function printFirstNegativeInteger(arr , n , k)
{
// A Double Ended Queue, Di that will
// store indexes of useful array elements
// for the current window of size k.
// The useful elements are all negative integers.
var Di = [];
// Process first k (or first window)
// elements of array
var i;
for (i = 0; i < k; i++)
// Add current element at the rear of Di
// if it is a negative integer
if (arr[i] < 0)
Di.push(i);
// Process rest of the elements,
// i.e., from arr[k] to arr[n-1]
for (; i < n; i++) {
// if Di is not empty then the element
// at the front of the queue is the first
// negative integer of the previous window
if (Di.length!==0)
document.write(arr[Di[0]] + " ");
// else the window does not have a
// negative integer
else
document.write("0" + " ");
// Remove the elements which are
// out of this window
while ((Di.length!==0) && Di[0] < (i - k + 1))
Di.shift(); // Remove from front of queue
// Add current element at the rear of Di
// if it is a negative integer
if (arr[i] < 0)
Di.push(i);
}
// Print the first negative
// integer of last window
if (Di.length !== 0)
document.write(arr[Di[0]] + " ");
else
document.write("0" + " ");
}
// Driver Code
var arr = [ 12, -1, -7, 8, -15, 30, 16, 28 ];
var n = arr.length;
var k = 3;
printFirstNegativeInteger(arr, n, k);
// This code is contributed by Rajput-Ji
</script>
Producción
-1 -1 -7 -15 -15 0
Complejidad de Tiempo: O(n), Espacio Auxiliar: O(k)
Enfoque optimizado : También es posible lograr esto con espacio constante. La idea es tener una variable firstNegativeIndex para realizar un seguimiento del primer elemento negativo en la ventana de tamaño k. En cada iteración, omitimos los elementos que ya no se encuentran dentro de la ventana de tamaño k actual (firstNegativeIndex <= i – k), así como los elementos no negativos (cero o positivo).
A continuación se muestra la solución basada en este enfoque.
C++
// C++ code for First negative integer
// in every window of size k
#include <iostream>
using namespace std;
void printFirstNegativeInteger(int arr[], int k, int n)
{
int firstNegativeIndex = 0;
int firstNegativeElement;
for (int i = k - 1; i < n; i++) {
// skip out of window and positive elements
while ((firstNegativeIndex < i)
&& (firstNegativeIndex <= i - k
|| arr[firstNegativeIndex] >= 0)) {
firstNegativeIndex++;
}
// check if a negative element is found, otherwise
// use 0
if (arr[firstNegativeIndex] < 0) {
firstNegativeElement = arr[firstNegativeIndex];
}
else {
firstNegativeElement = 0;
}
cout << firstNegativeElement << " ";
}
}
// Driver code
int main()
{
int arr[] = { 12, -1, -7, 8, -15, 30, 16, 28 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printFirstNegativeInteger(arr, k, n);
}
Java
// Java code for First negative integer
// in every window of size k
import java.util.*;
class GFG{
static void printFirstNegativeInteger(int arr[],
int k, int n)
{
int firstNegativeIndex = 0;
int firstNegativeElement;
for(int i = k - 1; i < n; i++)
{
// Skip out of window and positive elements
while ((firstNegativeIndex < i ) &&
(firstNegativeIndex <= i - k ||
arr[firstNegativeIndex] >= 0))
{
firstNegativeIndex ++;
}
// Check if a negative element is
// found, otherwise use 0
if (arr[firstNegativeIndex] < 0)
{
firstNegativeElement = arr[firstNegativeIndex];
}
else
{
firstNegativeElement = 0;
}
System.out.print(firstNegativeElement + " ");
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12, -1, -7, 8, -15, 30, 16, 28 };
int n = arr.length;
int k = 3;
printFirstNegativeInteger(arr, k, n);
}
}
// This code is contributed by amreshkumar3
Python3
# Python3 code for First negative integer # in every window of size k def printFirstNegativeInteger(arr, k): firstNegativeIndex = 0 for i in range(k - 1, len(arr)): # skip out of window and positive elements while firstNegativeIndex < i and (firstNegativeIndex <= i - k or arr[firstNegativeIndex] >= 0): firstNegativeIndex += 1 # check if a negative element is found, otherwise use 0 firstNegativeElement = arr[firstNegativeIndex] if arr[firstNegativeIndex] < 0 else 0 print(firstNegativeElement, end=' ') if __name__ == "__main__": arr = [12, -1, -7, 8, -15, 30, 16, 28] k = 3 printFirstNegativeInteger(arr, k) # contributed by Arjun Lather
C#
// C# code for First negative integer
// in every window of size k
using System;
class GFG{
static void printFirstNegativeInteger(int[] arr,
int k, int n)
{
int firstNegativeIndex = 0;
int firstNegativeElement;
for(int i = k - 1; i < n; i++)
{
// Skip out of window and positive elements
while ((firstNegativeIndex < i ) &&
(firstNegativeIndex <= i - k ||
arr[firstNegativeIndex] >= 0))
{
firstNegativeIndex ++;
}
// Check if a negative element is
// found, otherwise use 0
if (arr[firstNegativeIndex] < 0)
{
firstNegativeElement = arr[firstNegativeIndex];
}
else
{
firstNegativeElement = 0;
}
Console.Write(firstNegativeElement + " ");
}
}
// Driver code
static public void Main()
{
int[] arr = { 12, -1, -7, 8, -15, 30, 16, 28 };
int n = arr.Length;
int k = 3;
printFirstNegativeInteger(arr, k, n);
}
}
// This code is contributed by rag2127
Javascript
<script>
// JavaScript Program for the above approach
function printFirstNegativeInteger(arr, k, n) {
let firstNegativeIndex = 0;
let firstNegativeElement;
for (let i = k - 1; i < n; i++) {
// skip out of window and positive elements
while ((firstNegativeIndex < i) &&
(firstNegativeIndex <= i - k ||
arr[firstNegativeIndex] >= 0)) {
firstNegativeIndex++;
}
// check if a negative element is found, otherwise use 0
if (arr[firstNegativeIndex] < 0) {
firstNegativeElement = arr[firstNegativeIndex];
}
else {
firstNegativeElement = 0;
}
document.write(firstNegativeElement + " ");
}
}
// Driver code
let arr = [12, -1, -7, 8, -15, 30, 16, 28];
let n = arr.length;
let k = 3;
printFirstNegativeInteger(arr, k, n);
// This code is contributed by Potta Lokesh
</script>
Producción
-1 -1 -7 -15 -15 0
Complejidad de tiempo: O(n), Espacio auxiliar: O(1)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeek y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA