סכום המרכיבים המינימליים והמקסימליים של כל מערכי המשנה בגודל k


רמת קושי קשה
נשאל לעתים קרובות Byte קפיטל אחד קופון דוניה דאטבריקס Google Twilio Yandex
מערך תור חלון הזזה

הצהרת בעיה

הבעיה "סכום האלמנטים המינימליים והמקסימליים של כל מערכי המשנה בגודל k" קובעת שאתה מקבל מערך המכיל מספרים שלמים חיוביים ושליליים, מצא את סכום האלמנטים המינימליים והמקסימליים של כל מערכי המשנה בגודל k.

דוגמאות

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

הסבר
כל מערכי המשנה בגודל 4 הם,
{5, 9, 8, 3}: דקות + מקסימום = 9 + 3 = 12
{9, 8, 3, -4}: דקות + מקסימום = -4 + 9 = 5
{8, 3, -4, 2}: דקות + מקסימום = -4 + 8 = 4
{3, -4, 2, 1}: דקות + מקסימום = -4 + 3 = -1
{-4, 2, 1, -5}: דקות + מקסימום = -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

גישה

גישה נאיבית

חצו את כל מערכי המשנה בגודל k כדי למצוא את האלמנטים המינימליים והמקסימליים שלהם ולהדפיס את הסכום.

  1. אתחל סכום משתנה כ- 0.
  2. הפעל לולאה עבור i שווה 0 ל- (n - k), כאשר n הוא המספר הכולל של האלמנטים בנתון מערך. כל i משמש כנקודת ההתחלה של תת מערך בגודל k.
  3. הפעל לולאה מקוננת עבור j = i ל- (i + k) (לא כלול), לולאה זו מייצגת תת-מערך בגודל k. חצו את מערך המשנה הזה ומצאו את האלמנטים המינימליים והמקסימליים, שיהיו מינימום ומקסימום בהתאמה.
  4. הוסף (דקות + מקסימום) לסכום.
  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

ניתוח מורכבות

מורכבות זמן = 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. החלק האחורי של הדק d1 הוא אינדקס האלמנט המקסימלי של מערך המשנה והאחורי של הדק d2 הוא אינדקס האלמנט המינימלי של תת המערך. הוסף את סכום האלמנט המקסימלי והמינימלי לסכום המשתנה.
  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

ניתוח מורכבות

מורכבות זמן = O (n)
מורכבות שטח = O (n)
כאשר n הוא המספר הכולל של האלמנטים במערך הנתון.

כפי שהשתמשנו בתורים המייצגים את המספרים בסדר יורד וגדל, כך הם מאחסנים את האלמנטים פעם אחת. לפיכך האלגוריתם לוקח זמן ליניארי, וכך גם המרחב הנדרש הוא ליניארי.