Dada una array arr[] de tamaño N y un número entero K , la tarea es contar el número de elementos negativos presentes en todos los subarreglos de longitud K.
Ejemplo:
Entrada: arr[] = {-1, 2, -2, 3, 5, -7, -5}, K = 3
Salida: 2 1 1 1 2
Explicación:
Primer subarreglo: {-1, 2, -2} . Cuenta de números negativos = 2.
Segundo subarreglo: {2, -2, 3}. Conteo de números negativos = 1.
Tercer Subarreglo: {-2, 3, 5}. Conteo de números negativos = 1.
Cuarto Subarreglo: {3, 5, -7}. Conteo de números negativos = 1.
Quinto Subarreglo: {5, -7, -5}. Cuenta de números negativos = 2.Entrada: arr[] = {-1, 2, 4, 4}, K = 2
Salida: 1 0 0
Enfoque ingenuo: el enfoque más simple es recorrer la array dada , considerando cada ventana de tamaño K , y encontrar el recuento de números negativos en cada ventana.
Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)
Enfoque eficiente: este problema se puede resolver utilizando la técnica de deslizamiento de ventanas . Siga los pasos a continuación para resolver el problema:
- Inicialice una cuenta variable como 0 para almacenar la cuenta de elementos negativos en una ventana de tamaño K .
- Inicialice dos variables i y j como 0 para almacenar el primer y último índice de la ventana respectivamente.
- Bucle while j<N y realice los siguientes pasos:
- Si arr[j] < 0 , incrementa el conteo en 1.
- Si el tamaño de la ventana, es decir, j-i+1 es igual a K , imprima el valor de count y verifique si arr[i] < 0 , luego disminuya count en 1. Además, incremente i en 1.
- Incremente el valor de j en 1.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to count the number of
// negative elements in every window
// of size K
void countNegative(vector<int> arr, int k)
{
// Initialize the window pointers
int i = 0;
int j = 0;
// Store the count of negative numbers
int count = 0;
int n = arr.size();
// Traverse the array, arr[]
while (j < n)
{
// Increase the count
// if element is less then 0
if (arr[j] < 0)
{
count++;
}
// If size of the window equal to k
if (j - i + 1 == k)
{
cout << count << " ";
// If the first element of
// the window is less than 0,
// decrement count by 1
if (arr[i] < 0)
{
count--;
}
i++;
}
j++;
}
}
// Driver Code
int main()
{
// Given Input
vector<int> arr{ -1, 2, -2, 3, 5, -7, -5 };
int k = 3;
// Function Call
countNegative(arr, k);
}
// This code is contributed by bgangwar59
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to count the number of
// negative elements in every window
// of size K
public static void countNegative(int[] arr, int k)
{
// Initialize the window pointers
int i = 0;
int j = 0;
// Store the count of negative numbers
int count = 0;
int n = arr.length;
// Traverse the array, arr[]
while (j < n) {
// Increase the count
// if element is less then 0
if (arr[j] < 0) {
count++;
}
// If size of the window equal to k
if (j - i + 1 == k) {
System.out.print(count + " ");
// If the first element of
// the window is less than 0,
// decrement count by 1
if (arr[i] < 0) {
count--;
}
i++;
}
j++;
}
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int[] arr = { -1, 2, -2, 3, 5, -7, -5 };
int k = 3;
// Function Call
countNegative(arr, k);
}
}
Python3
# Function to count the number of # negative elements in every window # of size K def countNegative(arr,k): # Initialize the window pointers i = 0 j = 0 # Store the count of negative numbers count = 0 n = len(arr) while(j < n): # Increase the count # if element is less then 0 if (arr[j] < 0): count = count + 1 # If size of the window equal to k if (j - i + 1 == k): print(count,end=" ") # If the first element of # the window is less than 0, # decrement count by 1 if(arr[i] < 0): count = count - 1 i = i+1 j = j+1 # Driver Code # Given Input arr = [-1, 2, -2, 3, 5, -7, -5] k = 3 countNegative(arr, k) # This code is contributed by abhinavjain194.
C#
// C# program for the above approach
using System;
class GFG{
// Function to count the number of
// negative elements in every window
// of size K
public static void countNegative(int[] arr, int k)
{
// Initialize the window pointers
int i = 0;
int j = 0;
// Store the count of negative numbers
int count = 0;
int n = arr.Length;
// Traverse the array, arr[]
while (j < n)
{
// Increase the count
// if element is less then 0
if (arr[j] < 0)
{
count++;
}
// If size of the window equal to k
if (j - i + 1 == k)
{
Console.Write(count + " ");
// If the first element of
// the window is less than 0,
// decrement count by 1
if (arr[i] < 0)
{
count--;
}
i++;
}
j++;
}
}
// Driver Code
public static void Main(string[] args)
{
// Given Input
int[] arr = { -1, 2, -2, 3, 5, -7, -5 };
int k = 3;
// Function Call
countNegative(arr, k);
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of
// negative elements in every window
// of size K
function countNegative(arr, k)
{
// Initialize the window pointers
var i = 0;
var j = 0;
// Store the count of negative numbers
var count = 0;
var n = arr.length;
// Traverse the array, arr[]
while (j < n)
{
// Increase the count
// if element is less then 0
if (arr[j] < 0)
{
count++;
}
// If size of the window equal to k
if (j - i + 1 == k)
{
document.write( count + " ");
// If the first element of
// the window is less than 0,
// decrement count by 1
if (arr[i] < 0)
{
count--;
}
i++;
}
j++;
}
}
var arr = [ -1, 2, -2, 3, 5, -7, -5 ];
var k = 3;
// Function Call
countNegative(arr, k);
//This code is contributed by SoumikMondal
</script>
Producción:
2 1 1 1 2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)