Рубрики

Считать строго увеличивающиеся подмассивы

Учитывая массив целых чисел, подсчитайте количество подмассивов (размером более одного), которые строго увеличиваются.
Ожидаемая сложность времени: O (n)
Ожидаемое дополнительное пространство: O (1)

Примеры:

Input: arr[] = {1, 4, 3}
Output: 1
There is only one subarray {1, 4}

Input: arr[] = {1, 2, 3, 4}
Output: 6
There are 6 subarrays {1, 2}, {1, 2, 3}, {1, 2, 3, 4}
                      {2, 3}, {2, 3, 4} and {3, 4}

Input: arr[] = {1, 2, 2, 4}
Output: 2
There are 2 subarrays {1, 2} and {2, 4}

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Простое решение состоит в том, чтобы сгенерировать все возможные подмассивы , и для каждой подмассивы проверять, строго ли увеличивается подмассив или нет. В худшем случае временная сложность этого решения будет O (n 3 ).

Лучшее решение состоит в том, чтобы использовать тот факт, что если подмассив arr [i: j] не увеличивается строго, то подмассивы arr [i: j + 1], arr [i: j + 2], .. arr [i: n- 1] не может быть строго увеличивается. Ниже приведена программа, основанная на представленной выше идее.

C ++

// C ++ программа для подсчета количества строго
// увеличение подмассивов
#include<bits/stdc++.h>

using namespace std;

  

int countIncreasing(int arr[], int n)

{

    // Инициализируем количество подмассивов как 0

    int cnt = 0;

  

    // Выберите начальную точку

    for (int i=0; i<n; i++)

    {

        // Выбрать конечную точку

        for (int j=i+1; j<n; j++)

        {

            if (arr[j] > arr[j-1])

                cnt++;

  

            // Если подмассив arr [i..j] не строго

            // увеличивается, затем подмассивы после него, т.е.

            // arr [i..j + 1], arr [i..j + 2], .... не может

            // строго возрастать

            else

                break;

        }

    }

    return cnt;

}

  
// Драйвер программы

int main()

{

  int arr[] = {1, 2, 2, 4};

  int n = sizeof(arr)/sizeof(arr[0]);

  cout << "Count of strictly increasing subarrays is "

       << countIncreasing(arr, n);

  return 0;

}

Джава

// Java программа для подсчета количества строго
// увеличение подмассивов

  

  

class Test

{

    static int arr[] = new int[]{1, 2, 2, 4};

      

    static int countIncreasing(int n)

    {

        // Инициализируем количество подмассивов как 0

        int cnt = 0;

       

        // Выберите начальную точку

        for (int i=0; i<n; i++)

        {

            // Выбрать конечную точку

            for (int j=i+1; j<n; j++)

            {

                if (arr[j] > arr[j-1])

                    cnt++;

       

                // Если подмассив arr [i..j] не строго

                // увеличивается, затем подмассивы после него, т.е.

                // arr [i..j + 1], arr [i..j + 2], .... не может

                // строго возрастать

                else

                    break;

            }

        }

        return cnt;

    }

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        System.out.println("Count of strictly increasing subarrays is "

                                               countIncreasing(arr.length));

    }

}

python3

# Python3 программа для подсчета количества
Количество строго увеличивающихся подмассивов

  

def countIncreasing(arr, n):

      

    # Инициализировать количество подмассивов как 0

    cnt = 0

  

    # Выберите начальную точку

    for i in range(0, n) :

          

        # Выберите конечную точку

        for j in range(i + 1, n) :

            if arr[j] > arr[j - 1] :

                cnt += 1

  

            # Если подмассив arr [i..j] не является строго

            # увеличивается, затем подмассивы после него, т.е.

            # arr [i..j + 1], arr [i..j + 2], .... не может

            # строго возрастать

            else:

                break

    return cnt

  

  
# Код драйвера

arr = [1, 2, 2, 4]

n = len(arr)

print ("Count of strictly increasing subarrays is",

                            countIncreasing(arr, n))

  
# Этот код предоставлен Shreyanshi Arun.

C #

// C # программа для подсчета количества
// строго увеличивающиеся подмассивы

using System;

  

class Test

{

    static int []arr = new int[]{1, 2, 2, 4};

      

    static int countIncreasing(int n)

    {

        // Инициализируем количество подмассивов как 0

        int cnt = 0;

      

        // Выберите начальную точку

        for (int i = 0; i < n; i++)

        {

            // Выбрать конечную точку

            for (int j = i + 1; j < n; j++)

            {

                if (arr[j] > arr[j - 1])

                    cnt++;

      

                // Если подмассив arr [i..j] не строго

                // увеличивается, затем подмассивы после него,

                // то есть arr [i..j + 1], arr [i..j + 2], ....

                // не может быть строго увеличивается

                else

                    break;

            }

        }

        return cnt;

    }

      

    // Код драйвера

    public static void Main(String[] args) 

    {

        Console.Write("Count of strictly increasing"

            "subarrays is " + countIncreasing(arr.Length));

    }

}

  
// Этот код предоставлен parashar.

PHP

<?php
// PHP программа для подсчета количества
// строго увеличивающиеся подмассивы

  

function countIncreasing( $arr, $n)

{

      

    // Инициализировать количество подмассивов

    // как 0

    $cnt = 0;

  

    // Выберите начальную точку

    for ( $i = 0; $i < $n; $i++)

    {

        // Выбрать конечную точку

        for ( $j = $i+1; $j < $n; $j++)

        {

            if ($arr[$j] > $arr[$j-1])

                $cnt++;

  

            // Если подмассив arr [i..j] равен

            // не строго увеличивается,

            // затем подмассивы после него,

            // то есть arr [i..j + 1],

            // arr [i..j + 2], .... не могу

            // строго возрастать

            else

                break;

        }

    }

    return $cnt;

}

  
// Драйвер программы

  

$arr = array(1, 2, 2, 4);

$n = count($arr);

echo "Count of strictly increasing ",

                     "subarrays is ",

            countIncreasing($arr, $n);

  
// Этот код предоставлен anuj_67.
?>


Выход :

Count of strictly increasing subarrays is 2

Временная сложность вышеприведенного решения составляет O (m), где m — количество подмассивов в выходных данных.

Эта проблема и решение предоставлены Рахул Агравал.

Эффективное решение может подсчитать подмассивы за O (n) время. Идея основана на том факте, что отсортированный подмассив длины 'len' добавляет len * (len-1) / 2 к результату. Например, {10, 20, 30, 40} добавляет 6 к результату.

C ++

// C ++ программа для подсчета количества строго
// увеличение подмассивов за O (n) время.
#include<bits/stdc++.h>

using namespace std;

  

int countIncreasing(int arr[], int n)

{

    int cnt = 0;  // Инициализировать результат

  

    // Инициализируем длину текущего увеличения

    // подрешетка

    int len = 1;

  

    // Обход массива

    for (int i=0; i < n-1; ++i)

    {

        // Если arr [i + 1] больше, чем arr [i],

        // затем увеличиваем длину

        if (arr[i + 1] > arr[i])

            len++;

              

        // Остальное Обновить счетчик и сбросить длину

        else

        {

            cnt += (((len - 1) * len) / 2);

            len = 1;

        }

    }

      

    // Если последняя длина больше 1

    if (len > 1)

        cnt += (((len - 1) * len) / 2);

  

    return cnt;

}

  
// Драйвер программы

int main()

{

  int arr[] = {1, 2, 2, 4};

  int n = sizeof(arr)/sizeof(arr[0]);

  cout << "Count of strictly increasing subarrays is "

       << countIncreasing(arr, n);

  return 0;

}

Джава

// Java программа для подсчета количества строго
// увеличение подмассивов

  

  

class Test

{

    static int arr[] = new int[]{1, 2, 2, 4};

      

    static int countIncreasing(int n)

    {

        int cnt = 0// Инициализировать результат

           

        // Инициализируем длину текущего увеличения

        // подрешетка

        int len = 1;

       

        // Обход массива

        for (int i=0; i < n-1; ++i)

        {

            // Если arr [i + 1] больше, чем arr [i],

            // затем увеличиваем длину

            if (arr[i + 1] > arr[i])

                len++;

                   

            // Остальное Обновить счетчик и сбросить длину

            else

            {

                cnt += (((len - 1) * len) / 2);

                len = 1;

            }

        }

           

        // Если последняя длина больше 1

        if (len > 1)

            cnt += (((len - 1) * len) / 2);

       

        return cnt;

    }

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        System.out.println("Count of strictly increasing subarrays is "

                                               countIncreasing(arr.length));

    }

}

python3

# Python3 программа для подсчета количества
# строго увеличивающиеся подмассивы за O (n) время.

  

def countIncreasing(arr, n):

    cnt = 0 # Инициализировать результат

  

    # Инициализировать длину тока

    # увеличение подмассива

    len = 1

  

    # Пройти через массив

    for i in range(0, n - 1) :

          

        # Если arr [i + 1] больше, чем arr [i],

        # затем увеличить длину

        if arr[i + 1] > arr[i] :

            len += 1

              

        # Еще Обновление счетчика и сброса длины

        else:

            cnt += (((len - 1) * len) / 2)

            len = 1

      

    # Если последняя длина больше 1

    if len > 1:

        cnt += (((len - 1) * len) / 2)

  

    return cnt

  

  
# Драйверная программа

arr = [1, 2, 2, 4]

n = len(arr)

  

print ("Count of strictly increasing subarrays is",

                        int(countIncreasing(arr, n)))

  

  
# Этот код предоставлен Shreyanshi Arun.

C #

// C # программа для подсчета количества строго
// увеличение подмассивов

using System;

  

class GFG {

      

    static int []arr = new int[]{1, 2, 2, 4};

      

    static int countIncreasing(int n)

    {

        int cnt = 0; // Инициализировать результат

          

        // Инициализируем длину тока

        // увеличение подмассива

        int len = 1;

      

        // Обход массива

        for (int i = 0; i < n-1; ++i)

        {

              

            // Если arr [i + 1] больше чем

            // arr [i], затем увеличиваем длину

            if (arr[i + 1] > arr[i])

                len++;

                  

            // Остальное обновление счетчика и сброс

            // длина

            else

            {

                cnt += (((len - 1) * len) / 2);

                len = 1;

            }

        }

          

        // Если последняя длина больше 1

        if (len > 1)

            cnt += (((len - 1) * len) / 2);

      

        return cnt;

    }

      

    // Драйверный метод для проверки

    // вышеуказанная функция

    public static void Main() 

    {

        Console.WriteLine("Count of strictly "

                  + "increasing subarrays is "

               + countIncreasing(arr.Length));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для подсчета количества строго
// увеличение подмассивов за O (n) время.

  

function countIncreasing( $arr, $n)

{

      

    // Инициализировать результат

    $cnt = 0; 

  

    // Инициализируем длину

    // текущий рост

    // подрешетка

    $len = 1;

  

    // Обход массива

    for($i = 0; $i < $n - 1; ++$i)

    {

          

        // Если arr [i + 1] больше, чем arr [i],

        // затем увеличиваем длину

        if ($arr[$i + 1] > $arr[$i])

            $len++;

              

        // Остальное обновление счетчика и

        // сбросить длину

        else

        {

            $cnt += ((($len - 1) * $len) / 2);

            $len = 1;

        }

    }

      

    // Если последняя длина

    // более 1

    if ($len > 1)

        $cnt += ((($len - 1) * $len) / 2);

  

    return $cnt;

}

  
// Код драйвера

$arr = array(1, 2, 2, 4);

$n = count($arr);

echo "Count of strictly increasing subarrays is "

                     , countIncreasing($arr, $n);

  
// Этот код предоставлен anuj_67
?>


Выход :

Count of strictly increasing subarrays is 2

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Считать строго увеличивающиеся подмассивы

0.00 (0%) 0 votes