Рубрики

Количество подмассивов, чей минимум и максимум одинаковы

Задав массив из n целых чисел, найдите количество подмассивов, у которых минимальный и максимальный элементы совпадают. Подмассив определяется как непустая последовательность последовательных элементов.

Примеры :

Input: 2 3 1 1 
Output: 5
Explanation: The subarrays are (2), 
(3), (1), (1) and (1, 1) 

Input: 2 4 5 3 3 3
Output: 9
Explanation: The subarrays are (2), (4), 
(5), (3), (3, 3), (3, 3, 3), (3), (3, 3) and 
(3) 

Первое, на что нужно обратить внимание, это то, что только те подмассивы, у которых все элементы одинаковы, будут иметь одинаковые минимум и максимум. Наличие разных элементов явно означает разные минимум и максимум. Следовательно, нам просто нужно вычислить количество непрерывных одинаковых элементов (скажем, d) , а затем по формуле комбинации мы получим число подмассивов равным:

No of subarrays possible with d elements = ( d * (d+1) / 2 )
where d is number of continuous same elements.

Мы переходим от 1-n и затем от I + 1 к n, а затем находим число непрерывных одинаковых элементов и затем добавляем к результату невозможность подмассивов.

C ++

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

using namespace std;

  
// вычисляем количество смежных подмассивов
// который имеет одинаковый минимум и максимум

int calculate(int a[], int n)

{

    // сохраняет ответ

    int ans = 0;

  

    // цикл для перехода от 0-n

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

  

        // начинаем проверять подмассив следующего элемента

        int r = i + 1;

  

        // ход для поиска подмассивов

        for (int j = r; j < n; j++) {

  

            // если элементы одинаковы

            // проверяем дальше и держим счет

            // с одинаковыми номерами в 'r'

            if (a[i] == a[j])

                r += 1; 

            else

                break

        }

  

        // количество элементов между r и i

        // с такими же элементами.

        int d = r - i;

  

        // количество подмассивов, которые могут быть сформированы

        // между i и r

        ans += (d * (d + 1) / 2);

  

        // снова начинаем проверку со следующего индекса

        i = r - 1;

    }

  

    // возвращает ответ

    return ans;

}

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

int main()

{

    int a[] = { 2, 4, 5, 3, 3, 3 };

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

    cout << calculate(a, n);

    return 0;

}

Джава

// Java-программа для подсчета количества подмассивов
// имеющие одинаковый минимум и максимум.

  

class Subarray 

{

    // вычисляем количество смежных подмассивов

    // который имеет одинаковый минимум и максимум

    static int calculate(int a[], int n)

    {

        // сохраняет ответ

        int ans = 0;

  

        // цикл для перехода от 0-n

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

  

            // начинаем проверять подмассив из

            // следующий элемент

            int r = i + 1;

  

            // ход для поиска подмассивов

            for (int j = r; j < n; j++) {

  

                // если элементы одинаковы

                // проверяем дальше и сохраняем

                // количество одинаковых чисел в 'r'

                if (a[i] == a[j])

                    r += 1

                else

                    break

            }

  

            // количество элементов между r

            // и я с теми же элементами.

            int d = r - i;

  

            // нет. подмассивов, которые могут быть

            // сформирован между i и r

            ans += (d * (d + 1) / 2);

  

            // снова начинаем проверку со следующего

            // показатель

            i = r - 1;

        }

  

        // возвращает ответ

        return ans;

    }

      

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) 

    {

    int a[] = {  2, 4, 5, 3, 3, 3 };

    System.out.println(calculate(a, a.length));

    }

}
// Этот код предоставлен Prerna Saini

python3

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

  
# рассчитать число смежных
# подмассивы с одинаковыми
# минимум и максимум

def calculate(a, n):

      

    # хранит ответ

    ans = 0;

    i = 0;

  

    # цикл для перехода от 0-n

    while(i < n): 

          

        # начать проверку подмассива

        # от следующего элемента

        r = i + 1;

  

        # ход для

        # поиск подмассивов

        for j in range(r, n): 

              

            # если элементы одинаковы

            # тогда мы проверим дальше

            # и вести счет же

            # числа в 'r'

            if (a[i] == a[j]):

                r = r + 1

            else:

                break

  

        # количество элементов в

        # между г и я с

        # одинаковые элементы.

        d = r - i;

  

        # количество подмассивов, которые

        # может быть сформирован между i и r

        ans = ans + (d * (d + 1) / 2);

  

        # снова начать проверку

        # из следующего индекса

        i = r - 1;

        i = i + 1;

  

    # возвращает ответ

    return int(ans);

  
Код водителя

a = [ 2, 4, 5, 3, 3, 3 ];

n = len(a);

print(calculate(a, n));

  
# Этот код предоставлен mits

C #

// Программа для подсчета числа
// из подмассивов, имеющих одинаковые
// минимум и максимум.

using System;

  

class Subarray {

    // вычисляем число смежных

    // подмассивы с одинаковыми

    // минимум и максимум

    static int calculate(int[] a, int n)

    {

        // сохраняет ответ

        int ans = 0;

  

        // цикл для перехода от 0-n

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

  

            // начать проверку подмассива

            // из следующего элемента

            int r = i + 1;

  

            // ход для поиска подмассивов

            for (int j = r; j < n; j++) {

  

                // если элементы одинаковы

                // проверяем дальше и сохраняем

                // количество одинаковых чисел в 'r'

                if (a[i] == a[j])

                    r += 1;

                else

                    break;

            }

  

            // количество элементов между

            // r и i с одинаковыми элементами.

            int d = r - i;

  

            // нет. подмассивов, которые могут

            // сформироваться между i и r

            ans += (d * (d + 1) / 2);

  

            // снова начинаем проверку с

            // следующий индекс

            i = r - 1;

        }

  

        // возвращает ответ

        return ans;

    }

  

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

    public static void Main()

    {

        int[] a = { 2, 4, 5, 3, 3, 3 };

        Console.WriteLine(calculate(a, a.Length));

    }

}

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

PHP

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

  
// вычисляем число смежных
// подмассивы с одинаковым минимумом
// и максимум

function calculate($a, $n)

{

    // сохраняет ответ

    $ans = 0;

  

    // цикл для перехода от 0-n

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

    {

  

        // начать проверку подмассива

        // из следующего элемента

        $r = $i + 1;

  

        // ход для поиска подмассивов

        for ($j = $r; $j < $n; $j++) 

        {

  

            // если элементы одинаковые

            // тогда мы проверяем дальше и

            // вести подсчет одинаковых номеров

            // в 'r'

            if ($a[$i] == $a[$j])

                $r += 1; 

            else

                break

        }

  

        // количество элементов между

        // r и i с одинаковыми элементами.

        $d = $r - $i;

  

        // количество подмассивов, которые

        // может быть сформирован между i и r

        $ans += ($d * ($d + 1) / 2);

  

        // снова начинаем проверку

        // из следующего индекса

        $i = $r - 1;

    }

  

    // возвращает ответ

    return $ans;

}

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

$a = array( 2, 4, 5, 3, 3, 3 );

$n = count($a);

echo calculate($a, $n);

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


Выход :

9

Временная сложность: O (n)
Вспомогательное пространство: O (1)

Эта статья предоставлена Раджа Викрамадитья (Радж) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Количество подмассивов, чей минимум и максимум одинаковы

0.00 (0%) 0 votes