Ҷамъи унсурҳои минималӣ ва максималии ҳамаи зергурӯҳҳои андозаи k


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад ByteDance Пойтахт Яке аз КупонДуния Хиштҳо Google Тиллио Yandex
тартиботи ҳарбӣ навбат Равзанаи Sliding

Изҳороти мушкилот

Масъалаи "Ҷамъи унсурҳои минималӣ ва максималии ҳама зеркисматҳои андозаи k" мегӯяд, ки ба шумо массиви дорои бутунҳои мусбат ва манфӣ дода мешавад, ҷамъи унсурҳои минимум ва максималии ҳамаи зеркатроҳои андозаи k -ро ёбед.

Намунаҳои

arr[] = {5, 9, 8, 3, -4, 2, 1, -5}
k = 4
17

Шарҳ
Ҳама зерсатрҳои андозаи 4 инҳоянд,
{5, 9, 8, 3}: min + max = 9 + 3 = 12
{9, 8, 3, -4}: min + max = -4 + 9 = 5
{8, 3, -4, 2}: min + max = -4 + 8 = 4
{3, -4, 2, 1}: min + max = -4 + 3 = -1
{-4, 2, 1, -5}: min + max = -5 + 2 = -3

Ҷамъи унсурҳои минималӣ ва максималии ҳамаи зергурӯҳҳои андозаи k

arr[] = {1, -1, 2, -2, 3, -3}
k = 2
2

Шарҳ
Ҳама зерсатрҳои андозаи 2 инҳоянд,
{1, -1}: min + max = -1 + 1 = 0
{-1, 2}: min + max = -1 + 2 = 1
{2, -2}: min + max = -2 + 2 = 0
{-2, 3}: min + max = -2 + 3 = 1
{3, -3}: min + max = -3 + 3 = 0

усул

Усули соддалавҳона

Барои ёфтани унсурҳои минималӣ ва максималии онҳо ҳамаи зеркатрасаҳои андозаи k-ро убур кунед ва ҷамъбастро чоп кунед.

  1. Маблағи тағирёбандаро ҳамчун 0 оғоз кунед.
  2. Доираро барои i ба 0 ба (n - k) баробар иҷро кунед, ки n шумораи умумии элементҳои додашуда мебошад асал. Ҳар як i ҳамчун нуқтаи ибтидоии зерқатори андозаи k амал мекунад.
  3. Доираи лонаеро барои j = i ба (i + k) иҷро кунед (дохил карда нашудааст), ин ҳалқа зеркатри массиви андозаи k -ро нишон медиҳад. Ин зеркатрасурро убур кунед ва унсурҳои минимум ва максимумро ёбед, бигзор онҳо мутаносибан min ва max бошанд.
  4. Ба сум (min + max) илова кунед.
  5. Дар охири гардиш, маблағи баргардонед.

ки дар он n шумораи умумии элементҳо дар массиви додашуда мебошад.

Кодекси Java барои ёфтани Ҷамъи унсурҳои минималӣ ва максималии ҳамаи зергурӯҳҳои андозаи k

class SumOfMinimumAndMaximumElementsOfAllSubarraysOfSizeK {
    private static int sumOfMinMax(int[] arr, int k) {
        int n = arr.length;
        // initialize sum as 0
        int sum = 0;

        // Traverse all the subarray of size k one by one
        for (int i = 0; i <= n - k; i++) {
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            // traverse the current subarray and find the min and max
            for (int j = i; j < i + k; j++) {
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);
            }

            // add (min + max) to the sum
            sum += (min + max);
        }

        return sum;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 9, 8, 3, -4, 2, 1, -5};
        int k1 = 4;
        System.out.println(sumOfMinMax(arr1, k1));

        // Example 2
        int arr2[] = new int[]{1, -1, 2, -2, 3, -3};
        int k2 = 2;
        System.out.println(sumOfMinMax(arr2, k2));
    }
}
17
2

C ++ рамз барои дарёфти Ҷамъи унсурҳои ҳадди ақалл ва максималии ҳамаи зергурӯҳҳои андозаи k

#include<bits/stdc++.h> 
using namespace std; 

int sumOfMinMax(int *arr, int k, int n) {
    // initialize sum as 0
    int sum = 0;
    
    // Traverse all the subarray of size k one by one
    for (int i = 0; i <= (n - k); i++) {
        int min = INT_MAX;
        int max = INT_MIN;
        // traverse the current subarray and find the min and max
        for (int j = i; j < i + k; j++) {
            min = std::min(min, arr[j]);
            max = std::max(max, arr[j]);
        }
        
        // add (min + max) to the sum
        sum += (min + max);
    }
    
    return sum;
}

int main() {
    // Example 1
    int arr1[] = {5, 9, 8, 3, -4, 2, 1, -5};
    int k1 = 4;
    cout<<sumOfMinMax(arr1, k1, sizeof(arr1) / sizeof(arr1[0]))<<endl;

    // Example 2
    int arr2[] = {1, -1, 2, -2, 3, -3};
    int k2 = 2;
    cout<<sumOfMinMax(arr2, k2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
    
    return 0;
}
17
2

Таҳлили мураккабӣ

Мураккабии вақт = О (н * к)
Мураккабии фазо = О (1)

Дар ин ҷо мураккабии вақт полиномия аст, зеро мо мустақилона масъала барои ҳар як зеркатрасаро ҳал мекунем. Азбаски мо танҳо тағирёбандаем; y ду тағирёбанда барои ҳадди аксар ва ҳадди аққал, фазои зарурӣ доимист.

Усули оптималӣ

Ду созед Дек d1 ва d2, ҳарду дек индекси унсурҳоеро нигоҳ медоранд, ки метавонанд дар ҳадди ақалл ва ҳадди аксар зеркатрасон саҳм гузоранд. Deque d1 унсурҳоро бо тартиби камшавӣ аз пеш ба ақиб ва d2 унсурҳоро бо тартиби афзоиш аз пеш ба қафо дар бар мегирад.

  1. Маблағи тағирёбандаро ҳамчун 0. оғоз кунед. Ду деки d1 ва d2 созед. Зер-массиви якуми андозаи k-ро дида мебароем.
  2. Дар ҳоле ки унсури ҷории зеркатри андозаи k аз унсури дар индекси пушти d1 калон ё ба он баробар аст, унсури қафои Deque d1-ро хориҷ кунед.
  3. Дар ҳоле ки унсури ҷории зеркатри андозаи k аз унсури дар паси индекси d2 хурд ё ба он баробар аст, унсури паси Deque d2 -ро хориҷ кунед.
  4. Индекси ҳозираро ба қафои ҳарду дека илова кунед.
  5. Пушти deque d1 индекси унсури максималии зеркатро ва пушти de2 dXNUMX индекси минималии зеркатро ташкил медиҳанд. Ҷамъи элементи максимум ва минимумро ба суммаи тағирёбанда илова кунед.
  6. Суб-массивҳои боқимондаи андозаи k-ро убур кунед ва қадамҳои аз 2 то 5-ро такрор кунед. Барои ҳама зеркатроҳои боқимонда аз техникаи тирезаи лағжанда ва танҳо унсури дар зерқатори қаблӣ мавҷудбударо коркард кунед.
  7. Пас аз гузаштани ҳама зеркатрасмаҳо суммаро баргардонед.

Рамзи Java барои ёфтани Ҷамъи унсурҳои минималӣ ва максималии ҳамаи зергурӯҳҳои андозаи k

import java.util.Deque;
import java.util.LinkedList;

class SumOfMinimumAndMaximumElementsOfAllSubarraysOfSizeK {
    private static int sumOfMinMax(int[] arr, int k) {
        int n = arr.length;
        // initialize sum as 0
        int sum = 0;

        // create 2 deques d1 and d2
        Deque<Integer> d1 = new LinkedList<>();
        Deque<Integer> d2 = new LinkedList<>();

        // first subarray
        for (int i = 0; i < k; i++) {
            // only push the elements that may contribute to maximum
            while (!d1.isEmpty() && arr[d1.peekLast()] <= arr[i])
                d1.removeLast();

            // only push the elements that may contribute to minimum
            while (!d2.isEmpty() && arr[d2.peekLast()] >= arr[i])
                d2.removeLast();

            // add the current elememt's index
            d1.addLast(i);
            d2.addLast(i);
        }

        // sum of min and max for first subarray
        sum += arr[d2.peekFirst()] + arr[d1.peekFirst()];

        // traverse the remaining subarray
        for (int i = k; i < n; i++) {
            // remove the previous element (sliding window technique)
            while (!d2.isEmpty() && d2.peekFirst() <= i - k)
                d2.removeFirst();
            while (!d1.isEmpty() && d1.peekFirst() <= i - k)
                d1.removeFirst();

            // only push the elements that may contribute to maximum
            while (!d1.isEmpty() && arr[d1.peekLast()] <= arr[i])
                d1.removeLast();

            // only push the elements that may contribute to minimum
            while (!d2.isEmpty() && arr[d2.peekLast()] >= arr[i])
                d2.removeLast();

            // add the current element's index
            d1.addLast(i);
            d2.addLast(i);

            // sum of min and max for current subarray
            sum += arr[d2.peekFirst()] + arr[d1.peekFirst()];
        }

        // return total sum
        return sum;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 9, 8, 3, -4, 2, 1, -5};
        int k1 = 4;
        System.out.println(sumOfMinMax(arr1, k1));

        // Example 2
        int arr2[] = new int[]{1, -1, 2, -2, 3, -3};
        int k2 = 2;
        System.out.println(sumOfMinMax(arr2, k2));
    }
}
17
2

C ++ рамз барои дарёфти Ҷамъи унсурҳои ҳадди ақалл ва максималии ҳамаи зергурӯҳҳои андозаи k

#include<bits/stdc++.h> 
using namespace std; 

int sumOfMinMax(int *arr, int k, int n) {
    // initialize sum as 0
    int sum = 0;
    
    // create 2 deques d1 and d2
    deque<int> d1;
    deque<int> d2;
    
    // first subarray
    for (int i = 0; i < k; i++) {
        // only push the elements that may contribute to maximum
        while (!d1.empty() && arr[d1.back()] <= arr[i]) {
            d1.pop_back();
        }
        
        // only push the elements that may contribute to minimum
        while (!d2.empty() && arr[d2.back()] >= arr[i]) {
            d2.pop_back();
        }
        
        // add the current element's index
        d1.push_back(i);
        d2.push_back(i);
    }
    
    // sum of min and max for first subarray
    sum += (arr[d2.front()] + arr[d1.front()]);
    
    // traverse the remaining subarray
    for (int i = k; i < n; i++) {
        // remove the previous element (sliding window technique)
        while (!d1.empty() && d1.front() <= (i -k)) {
            d1.pop_front();
        }
        while (!d2.empty() && d2.front() <= (i - k)) {
            d2.pop_front();
        }
        
        // only push the elements that may contribute to maximum
        while (!d1.empty() && arr[d1.back()] <= arr[i]) {
            d1.pop_back();
        }
        
        // only push the elements that may contribute to minimum
        while (!d2.empty() && arr[d2.back()] >= arr[i]) {
            d2.pop_back();
        }
        
        // add the current element's index
        d1.push_back(i);
        d2.push_back(i);
        
        // sum of min and max for current subarray
        sum += (arr[d1.front()] + arr[d2.front()]);
    }
    
    // return total sum
    return sum;
}

int main() {
    // Example 1
    int arr1[] = {5, 9, 8, 3, -4, 2, 1, -5};
    int k1 = 4;
    cout<<sumOfMinMax(arr1, k1, sizeof(arr1) / sizeof(arr1[0]))<<endl;

    // Example 2
    int arr2[] = {1, -1, 2, -2, 3, -3};
    int k2 = 2;
    cout<<sumOfMinMax(arr2, k2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
    
    return 0;
}
17
2

Таҳлили мураккабӣ

Мураккабии вақт = Эй (н)
Мураккабии фазо = Эй (н)
ки дар он n шумораи умумии элементҳо дар массиви додашуда мебошад.

Тавре ки мо навбатҳоеро истифода кардем, ки рақамҳоро бо тартиби кам ва афзоиш нишон медиҳанд, аз ин рӯ онҳо унсурҳоро якбора нигоҳ медоранд. Ҳамин тариқ, алгоритм вақти хатиро мегирад ва аз ин рӯ фазои зарурӣ низ хатӣ аст.