Различия между количеством увеличивающихся подмассивов и уменьшающихся подмассивов в окнах размера k

Опубликовано: 6 Января, 2022

Для массива целых чисел и k найдите разницу между числом строго возрастающих подмассивов (размером больше единицы) и числом строго убывающих подмассивов в окне размера k.
Примеры:

 Ввод: числа = {10, 20, 30, 15, 15}; 
           k = 3; 
Выход: 3, 0, -1 
Объяснение 
Для первого окна [10, 20, 30] есть 
3 возрастающих поддиапазона ([10, 20, 30], [10, 20], 
и [20, 30]) и 0 убывает, поэтому ответ 
равно 3. Для второго окна [20, 30, 15], 
есть 1 возрастающий поддиапазон и 1 убывающий, 
так что ответ - 0. Для третьего окна 
[20, 15, 15], есть 1 убывающий поддиапазон 
и 0 увеличивается, поэтому ответ -1.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Нам нужно вычислить разницу между увеличивающимися и уменьшающимися подмассивами для каждого окна размера K. Мы перебираем массив и для каждого окна размера k мы вычисляем количество увеличивающихся и уменьшающихся подмассивов и вставляем разницу между ними. в выходном массиве.

Создайте два массива размера N, инициализируйте их нулем и создайте выходной массив.
Итерировать по массиву
Вычислить количество увеличивающихся подмассивов
Вычислить убывающие подмассивы
Вставьте разницу между увеличением и уменьшением подмассивов в выходной массив.

Время Сложность решения - O (n * k)
n = Размер массива
k = размер окна

C ++

 // CPP program to count the differenes
 #include <iostream>
 #include <vector>
 using namespace std;
 // function to calculate the diffrence
 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 program to count the differenes
 import java.util.*;
 class GFG
 {
 // function to calculate the diffrence
 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 diffrence
 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 differenes
 using System;
 using System.Collections.Generic;
 class GFG
 {
 // function to calculate the diffrence
 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 differenes
 // function to calculate the diffrence
 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>

Выход:

3, 0, -1,

Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Разница между

Различия между количеством увеличивающихся подмассивов и уменьшающихся подмассивов в окнах размера k

C ++

Джава

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ