Dada una array de enteros y k, encuentre la diferencia entre el número de subarreglos estrictamente crecientes (de tamaño superior a uno) y el número de subarreglos estrictamente decrecientes en la ventana de tamaño k.
Ejemplos:
Input : nums = {10, 20, 30, 15, 15};
k = 3;
Output : 3, 0, -1
Explanation
For the first window of [10, 20, 30], there are
3 increasing subranges ([10, 20, 30], [10, 20],
and [20, 30]) and 0 decreasing, so the answer
is 3. For the second window of [20, 30, 15],
there is 1 increasing subrange and 1 decreasing,
so the answer is 0. For the third window of
[20, 15, 15], there is 1 decreasing subrange
and 0 increasing, so the answer is -1.
Necesitamos calcular la diferencia entre los subarreglos crecientes y decrecientes para cada una de las ventanas de tamaño K. Iteramos a través de la array y para cada ventana de tamaño k, calculamos el número de subarreglos crecientes y decrecientes e insertamos la diferencia de ellos en la array de salida.
- Cree dos arrays de tamaño N e inicialícelas en cero y cree la array de salida.
- Iterar a través de la array
- Calcular el número de subarreglos crecientes
- Calcular los subarreglos decrecientes
- Inserte la diferencia entre subarreglos crecientes y decrecientes en la array de salida.
Tiempo Complejidad de la solución: O(n*k)
n = Tamaño de la array
k = Tamaño de la ventana
Implementación:
C++
// CPP program to count the differences
#include <iostream>
#include <vector>
using namespace std;
// function to calculate the difference
vector<int> Diffs(vector<int> const& a, int k)
{
vector<int> out;
vector<int> inc, dec;
// initializing inc and dec with 0 and resizing
// equal to the size of main array
inc.resize(a.size(), 0);
dec.resize(a.size(), 0);
int inc_sum = 0;
int dec_sum = 0;
// iterate through the array
for (int i = 0; i < a.size(); ++i) {
// finding number of increasing
// subarrays in a window size k
for (int j = i - 1; j >= 0 && j > i - k &&
a[j + 1] > a[j]; --j) {
++inc[j];
++inc_sum;
}
// Finding number of decreasing subarrays
// in a window size k
for (int j = i - 1; j >= 0 && j > i - k &&
a[j + 1] < a[j]; --j) {
++dec[j];
++dec_sum;
}
// calculate the difference
if (i >= k - 1) {
// if this is not the first window then
// calculate inc_sum and dec_sum
if (i >= k) {
inc_sum -= inc[i - k];
dec_sum -= dec[i - k];
}
// insert the difference in k size window
// in the output vector
out.push_back(inc_sum - dec_sum);
}
}
return out;
}
// driver program
int main()
{
vector<int> out = Diffs({ 10, 20, 30, 15, 15}, 3);
for (int n : out)
cout << n << ", ";
return 0;
}
Java
// JAVA program to count the differences
import java.util.*;
class GFG
{
// function to calculate the difference
static Vector<Integer> Diffs(int []a, int k)
{
Vector<Integer> out = new Vector<Integer>();
int [] inc, dec;
// initializing inc and dec with 0 and resizing
// equal to the size of main array
inc = new int[a.length];
dec = new int[a.length];
int inc_sum = 0;
int dec_sum = 0;
// iterate through the array
for (int i = 0; i < a.length; ++i)
{
// finding number of increasing
// subarrays in a window size k
for (int j = i - 1; j >= 0 && j > i - k &&
a[j + 1] > a[j]; --j)
{
++inc[j];
++inc_sum;
}
// Finding number of decreasing subarrays
// in a window size k
for (int j = i - 1; j >= 0 && j > i - k &&
a[j + 1] < a[j]; --j)
{
++dec[j];
++dec_sum;
}
// calculate the difference
if (i >= k - 1)
{
// if this is not the first window then
// calculate inc_sum and dec_sum
if (i >= k)
{
inc_sum -= inc[i - k];
dec_sum -= dec[i - k];
}
// insert the difference in k size window
// in the output vector
out.add(inc_sum - dec_sum);
}
}
return out;
}
// Driver code
public static void main(String[] args)
{
int []arr = { 10, 20, 30, 15, 15};
Vector<Integer>out = Diffs(arr, 3);
for (int n : out)
System.out.print(n + ", ");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to count the differences # Function to calculate the difference def Diffs(a, k): out, inc, dec = [], [0] * len(a), [0] * len(a) # Initializing inc and dec with 0 and # resizing equal to the size of main array inc_sum, dec_sum = 0, 0 # Iterate through the array for i in range(0, len(a)): # Finding number of increasing # subarrays in a window size k j = i - 1 while (j >= 0 and j > i - k and a[j + 1] > a[j]): inc[j] += 1 inc_sum += 1 j -= 1 # Finding number of decreasing # subarrays in a window size k j = i - 1 while (j >= 0 and j > i - k and a[j + 1] < a[j]): dec[j] += 1 dec_sum += 1 j -= 1 # calculate the difference if i >= k - 1: # if this is not the first window then # calculate inc_sum and dec_sum if i >= k: inc_sum -= inc[i - k] dec_sum -= dec[i - k] # insert the difference in k size window # in the output vector out.append(inc_sum - dec_sum) return out # Driver Code if __name__ == "__main__": out = Diffs([10, 20, 30, 15, 15], 3) for n in out: print(n, end = ", ") # This code is contributed by Rituraj Jain
C#
// C# program to count the differences
using System;
using System.Collections.Generic;
class GFG
{
// function to calculate the difference
static List<int> Diffs(int []a, int k)
{
List<int> Out = new List<int>();
int [] inc, dec;
// initializing inc and dec with 0 and resizing
// equal to the size of main array
inc = new int[a.Length];
dec = new int[a.Length];
int inc_sum = 0;
int dec_sum = 0;
// iterate through the array
for (int i = 0; i < a.Length; ++i)
{
// finding number of increasing
// subarrays in a window size k
for (int j = i - 1; j >= 0 && j > i - k &&
a[j + 1] > a[j]; --j)
{
++inc[j];
++inc_sum;
}
// Finding number of decreasing subarrays
// in a window size k
for (int j = i - 1; j >= 0 && j > i - k &&
a[j + 1] < a[j]; --j)
{
++dec[j];
++dec_sum;
}
// calculate the difference
if (i >= k - 1)
{
// if this is not the first window then
// calculate inc_sum and dec_sum
if (i >= k)
{
inc_sum -= inc[i - k];
dec_sum -= dec[i - k];
}
// insert the difference in k size window
// in the output vector
Out.Add(inc_sum - dec_sum);
}
}
return Out;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 10, 20, 30, 15, 15};
List<int>Out = Diffs(arr, 3);
foreach (int n in Out)
Console.Write(n + ", ");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Js program to count the differences
// function to calculate the difference
function Diffs( a, k)
{
let out = [];
let inc, dec;
// initializing inc and dec with 0 and resizing
// equal to the size of main array
inc = [];
dec = [];
for(let i = 0;i<a.length;i++){
inc.push(0);
dec.push(0);
}
let inc_sum = 0;
let dec_sum = 0;
// iterate through the array
for (let i = 0; i < a.length; ++i) {
// finding number of increasing
// subarrays in a window size k
for (let j = i - 1; j >= 0 && j > i - k &&
a[j + 1] > a[j]; --j) {
++inc[j];
++inc_sum;
}
// Finding number of decreasing subarrays
// in a window size k
for (let j = i - 1; j >= 0 && j > i - k &&
a[j + 1] < a[j]; --j) {
++dec[j];
++dec_sum;
}
// calculate the difference
if (i >= k - 1) {
// if this is not the first window then
// calculate inc_sum and dec_sum
if (i >= k) {
inc_sum -= inc[i - k];
dec_sum -= dec[i - k];
}
// insert the difference in k size window
// in the output vector
out.push(inc_sum - dec_sum);
}
}
return out;
}
// driver program
let out = Diffs([10, 20, 30, 15, 15], 3);
document.write(out)
// This code is contributed by rohitsingh07052.
</script>
Producción:
3, 0, -1,
Publicación traducida automáticamente
Artículo escrito por niteesh_Kr y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA