Рубрики

Найти подмассив с наименьшим средним

Дан массив arr [] размера n и целого числа k такой, что k <= n.

Примеры :

Input:  arr[] = {3, 7, 90, 20, 10, 50, 40}, k = 3
Output: Subarray between indexes 3 and 5
The subarray {20, 10, 50} has the least average 
among all subarrays of size 3.

Input:  arr[] = {3, 7, 5, 20, -10, 0, 12}, k = 2
Output: Subarray between [4, 5] has minimum average

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

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

Эффективное решение состоит в том, чтобы решить вышеупомянутую проблему в O (n) времени и O (1) дополнительном пространстве. Идея состоит в том, чтобы использовать скользящее окно размера k. Следите за суммой текущих k элементов. Чтобы вычислить сумму текущего окна, удалите первый элемент предыдущего окна и добавьте текущий элемент (последний элемент текущего окна).

1) Initialize res_index = 0 // Beginning of result index
2) Find sum of first k elements. Let this sum be 'curr_sum'
3) Initialize min_sum = sum
4) Iterate from (k+1)'th to n'th element, do following
   for every element arr[i]
      a) curr_sum = curr_sum + arr[i] - arr[i-k]
      b) If curr_sum < min_sum
           res_index = (i-k+1)
5) Print res_index and res_index+k-1 as beginning and ending
   indexes of resultant subarray.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

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

using namespace std;

  
// Печатает начальный и конечный индексы подмассива
// размера k с минимальным средним

void findMinAvgSubarray(int arr[], int n, int k)

{

    // k должно быть меньше или равно n

    if (n < k)

        return;

  

    // Инициализировать начальный индекс результата

    int res_index = 0;

  

    // Вычисляем сумму первого подмассива размера k

    int curr_sum = 0;

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

        curr_sum += arr[i];

  

    // Инициализируем минимальную сумму как текущую сумму

    int min_sum = curr_sum;

  

    // Переход от (k + 1) -го элемента к n-му элементу

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

        // Добавить текущий элемент и удалить первый элемент

        // предыдущий подмассив

        curr_sum += arr[i] - arr[i - k];

  

        // Обновить результат, если необходимо

        if (curr_sum < min_sum) {

            min_sum = curr_sum;

            res_index = (i - k + 1);

        }

    }

  

    cout << "Subarray between [" << res_index << ", "

         << res_index + k - 1 << "] has minimum average";

}

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

int main()

{

    int arr[] = { 3, 7, 90, 20, 10, 50, 40 };

    int k = 3; // Размер подмассива

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

    findMinAvgSubarray(arr, n, k);

    return 0;

}

Джава

// Простая Java-программа для поиска
// минимальная средняя подрешетка

  

class Test {

      

    static int arr[] = new int[] { 3, 7, 90, 20, 10, 50, 40 };

  

    // Печатает начальный и конечный индексы подмассива

    // размера k с минимальным средним

    static void findMinAvgSubarray(int n, int k)

    {

        // k должно быть меньше или равно n

        if (n < k)

            return;

  

        // Инициализировать начальный индекс результата

        int res_index = 0;

  

        // Вычисляем сумму первого подмассива размера k

        int curr_sum = 0;

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

            curr_sum += arr[i];

  

        // Инициализируем минимальную сумму как текущую сумму

        int min_sum = curr_sum;

  

        // Переход от (k + 1) -го элемента к n-му элементу

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

        {

            // Добавить текущий элемент и удалить сначала

            // элемент предыдущего подмассива

            curr_sum += arr[i] - arr[i - k];

  

            // Обновить результат, если необходимо

            if (curr_sum < min_sum) {

                min_sum = curr_sum;

                res_index = (i - k + 1);

            }

        }

  

        System.out.println("Subarray between [" +

                            res_index + ", " + (res_index + k - 1) +

                            "] has minimum average");

    }

  

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

    public static void main(String[] args)

    {

        int k = 3; // Размер подмассива

        findMinAvgSubarray(arr.length, k);

    }

}

python3

# Python3 программа для поиска
# минимальный средний подмассив

  
# Печатает начало и конец
# индексы подмассива размера k
# с минимальным средним

def findMinAvgSubarray(arr, n, k):

  

    # k должно быть меньше или равно n

    if (n < k): return 0

  

    # Инициализировать начальный индекс результата

    res_index = 0

  

    # Вычислить сумму первого подмассива размера k

    curr_sum = 0

    for i in range(k):

        curr_sum += arr[i]

  

    # Инициализировать минимальную сумму как текущую сумму

    min_sum = curr_sum

  

    # Траверс от (k + 1) 'го

    # элемент к n-му элементу

    for i in range(k, n):

      

        # Добавить текущий элемент и удалить сначала

        # элемент предыдущего подмассива

        curr_sum += arr[i] - arr[i-k]

  

        # Обновить результат при необходимости

        if (curr_sum < min_sum):

          

            min_sum = curr_sum

            res_index = (i - k + 1)

          

    print("Subarray between [", res_index,

          ", ", (res_index + k - 1),

          "] has minimum average")

  
Код водителя

arr = [3, 7, 90, 20, 10, 50, 40]

k = 3 # Размер подмассива

n = len(arr)

findMinAvgSubarray(arr, n, k)

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

C #

// Простая программа на C # для поиска
// минимальная средняя подрешетка

using System;

  

class Test {

      

    static int[] arr = new int[] { 3, 7, 90, 20, 10, 50, 40 };

  

    // Печатает начальный и конечный индексы подмассива

    // размера k с минимальным средним

    static void findMinAvgSubarray(int n, int k)

    {

        // k должно быть меньше или равно n

        if (n < k)

            return;

  

        // Инициализировать начальный индекс результата

        int res_index = 0;

  

        // Вычисляем сумму первого подмассива размера k

        int curr_sum = 0;

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

            curr_sum += arr[i];

  

        // Инициализируем минимальную сумму как текущую сумму

        int min_sum = curr_sum;

  

        // Переход от (k + 1) -го элемента к n-му элементу

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

        {

            // Добавить текущий элемент и удалить первый элемент

            // предыдущий подмассив

            curr_sum += arr[i] - arr[i - k];

  

            // Обновить результат, если необходимо

            if (curr_sum < min_sum) {

                min_sum = curr_sum;

                res_index = (i - k + 1);

            }

        }

  

        Console.Write("Subarray between [" + res_index + ", " +

                     (res_index + k - 1) + 

                     "] has minimum average");

    }

  

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

    public static void Main()

    {

        int k = 3; // Размер подмассива

        findMinAvgSubarray(arr.Length, k);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Простая PHP-программа для поиска
// минимальная средняя подрешетка

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

function findMinAvgSubarray($arr, $n, $k)

{

      

    // k должно быть меньше

    // чем или равно n

    if ($n < $k)

        return;

  

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

    // индекс результата

    $res_index = 0;

  

    // Вычисляем сумму первого

    // подрешетка размера k

    $curr_sum = 0;

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

        $curr_sum += $arr[$i];

  

    // Инициализируем минимальную сумму

    // как текущая сумма

    $min_sum = $curr_sum;

  

    // Переход от (k + 1) -го элемента

    // к n-му элементу

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

    {

          

        // Добавить текущий элемент и

        // удалить первый элемент

        // предыдущий подмассив

        $curr_sum += $arr[$i] - $arr[$i - $k];

  

        // Обновить результат, если необходимо

        if ($curr_sum < $min_sum) {

            $min_sum = $curr_sum;

            $res_index = ($i - $k + 1);

        }

    }

  

    echo "Subarray between [" ,$res_index 

          , ", " ,$res_index + $k - 1, "] has minimum average";

}

  

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

    $arr = array(3, 7, 90, 20, 10, 50, 40);

      

    // Размер подмассива

    $k = 3; 

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

    findMinAvgSubarray($arr, $n, $k);

    return 0;

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


Выход:

Subarray between [3, 5] has minimum average

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

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

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

Найти подмассив с наименьшим средним

0.00 (0%) 0 votes