K өлчөмүндөгү бардык ич ара массивдердин минималдуу жана максималдуу элементтеринин суммасы


Кыйынчылык деңгээли катуу
Көп суралган ByteDance Capital One CouponDunia Databricks Гугл Twilio Яндекс
согуштук тизме кезек Жылма терезе

Маселени билдирүү

“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}: мин + макс = -1 + 1 = 0
{-1, 2}: мин + макс = -1 + 2 = 1
{2, -2}: мин + макс = -2 + 2 = 0
{-2, 3}: мин + макс = -2 + 3 = 1
{3, -3}: мин + макс = -3 + 3 = 0

жакындоо

Naive Appocach

K өлчөмүндөгү бардык суб-массивдерди кыдырып, алардын минималдуу жана максималдуу элементтерин таап, суммасын чыгарыңыз.

  1. 0 деп өзгөрүлмө сумманы баштаңыз.
  2. I үчүн 0-ге (n - k) барабар цикл жүргүзүңүз, мында n - берилген элементтердин жалпы саны согуштук тизме. Ар бир i көлөмү кичи массивдин баштапкы чекитинин милдетин аткарат.
  3. J = i ден (i + k) чейин (камтылбаган) ичтелген циклди иштетүү, бул цикл k өлчөмүндөгү кичи массивди билдирет. Бул суб-массивди айланып өтүп, минималдуу жана максималдуу элементтерди табыңыз, алар минималдуу жана максималдуу болсун.
  4. Кошумчага (min + max) кошуңуз.
  5. Жолдун аягында сумманы кайтарыңыз.

мында n - берилген массивдеги элементтердин жалпы саны.

K өлчөмүндөгү бардык кичи ичмектердин минималдуу жана максималдуу элементтеринин суммасын табуу үчүн Java коду

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

С ++ коду, 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

Комплекстик анализ

Убакыт татаалдыгы = O (n * k)
Космостун татаалдыгы = O (1)

Бул жерде убакыттын татаалдыгы көп мүчөлүү, анткени биз ар бир суб-массив үчүн маселени өз алдынча чечебиз. Биз эки гана өзгөрмөнү сактап келгендиктен, максималдуу жана минималдуу, талап кылынган орун туруктуу.

Оптималдуу ыкма

Эки түзүңүз Deque d1 жана d2, экилик тең массивдин минимумуна жана максимумуна өбөлгө түзө турган элементтердин индекстерин сактайт. Deque d1 элементтерди алдыдан артка карай азайтуу тартибинде, ал эми d2де алдыдан артка карай өсүү тартибиндеги элементтер бар.

  1. Өзгөрмө сумманы 0 деп инициализациялаңыз. D1 жана d2 эки декасын түзүңүз. K өлчөмүнүн биринчи суб-массивин карап көрөлү.
  2. K өлчөмүндөгү кичи массивдин учурдагы элементи d1 индексинин арткы бөлүгүндөгү элементтен чоң же ага тең болсо, Deque d1 арткы элементин алып салыңыз.
  3. K өлчөмүндөгү кичи массивдин учурдагы элементи d2 индексинин артындагы элементтен кичине же ага тең болсо, Deque d2дин арткы элементин алып салыңыз.
  4. Учурдагы индексти эки декинин артына кошуңуз.
  5. De1 арткы суб-массивдин максимум элементинин индекси, ал эми d2 deque арткы суб-массивдин минималдуу элементинин индекси. Максимум жана минималдуу элементтин суммасын өзгөрүлмө суммага кошуңуз.
  6. K өлчөмүндөгү калган суб-массивдерди айланып өтүп, 2-5 кадамдарды кайталаңыз. Калган бардык суб-массивдер үчүн жылып турган терезе техникасы жана мурунку суб-массивде жок элементти гана иштетүү.
  7. Бардык суб-массивдерди аралап өткөндөн кийин, сумманы кайтарыңыз.

K өлчөмүндөгү бардык кичи ичмектердин минималдуу жана максималдуу элементтеринин суммасын табуу үчүн Java коду

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

С ++ коду, 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

Комплекстик анализ

Убакыт татаалдыгы = O (N)
Космостун татаалдыгы = O (N)
мында n - берилген массивдеги элементтердин жалпы саны.

Сандарды азайып жана көбөйүү тартибинде көрсөткөн кезектерди колдонгондой эле, алар элементтерди бир жолу сакташат. Ошентип, алгоритм сызыктуу убакытты талап кылат, демек, талап кылынган мейкиндик да сызыктуу болот.