ماپ ڪ جي سڀني ذيلي حصن جي گهٽ ۾ گهٽ ۽ وڌ ۾ وڌ عناصر


تڪليف جي سطح سخت
بار بار پڇڻ ۾ ByteDance گاديء جو هڪ ڪوپن ڊنيا بنيادي دستاويزن گوگل Twilio ياندڪس
ڪيريو پنگتي حيثيت رکي ٿو سلائيڊ ونڊو

مسئلي جو بيان

مسئلو "ڪي ڪي سائيز جي تمام ننaysن حصن جو گهٽ ۾ گهٽ ۽ وڌ کان وڌ عنصر" بيان ڪري ٿو ته توهان کي صف ۽ منفي عددن تي مشتمل عدد ڏني وئي آهي ، قد جي سڀني سب تارن جي وڌ ۾ وڌ ۽ وڌ ۾ وڌ عناصر جو مجموعو ڳوليو.

مثال

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

ماپ ڪ جي سڀني ذيلي حصن جي گهٽ ۾ گهٽ ۽ وڌ ۾ وڌ عناصر

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

چرچو

نائي اچڻ وارو

انهن جي گهٽ کان گهٽ ۽ وڌ ۾ وڌ عنصر ڳولڻ لاءِ ۽ رقم ڇپائڻ لاءِ ڪ جي ماپ جي تمام ذيلي قطارون ڳوليو.

  1. شروعاتي طور تي 0 طور تي متغير رقم
  2. منهنجي لاءِ لوپ هلائيندڙ 0 جي (n - k) برابر آهي ، جتي n ڏنل عناصر جي ڪل تعداد آهي صف. هر آئون سائز ڪي جي ذيلي قطار جي شروعاتي نقطي جي طور تي ڪم ڪندو آهيان.
  3. j = i کان (i + k) لاءِ شامل ٿيل لوپ هلائڻ (شامل نه آھي) ، ھي لوپ ڪ جي ھڪڙي ذيلي قطار جي نمائندگي ڪري ٿو. هن ذيلي قطار کي لڪايو ۽ گهٽ ۾ گهٽ ۽ وڌ ۾ وڌ عنصر ڳوليو ، ترتيب ڏيو انهن کي گهٽ ۾ گهٽ ۽ وڌ ۾ وڌ.
  4. شامل ڪريو (منٽ + وڌ) رقم.
  5. سفري جي آخر ۾ ، واپسيءَ جي رقم.

جتي ڏنل ڏنل صف ۾ عناصر جو ڪل تعداد.

جاوا ڪوڊ سائيز جي سڀني ذيلي حصن جي گهٽ ۾ گهٽ ۽ وڌ ۾ وڌ عناصر کي ڳولڻ لاءِ

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

سي ++ ڪوڊ ڳولڻ جي نن subن نن maximumن ننaysن ننaysن عناصر جي مقدار کي گهٽ ۾ گهٽ ۽ وڌ ۾ وڌ شي

#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 ٻن متغيرن وڌ کان وڌ ۽ گهٽ حد تائين ، گهربل جڳهه مستقل آهي.

ڪوشان وارو رستو

ٻه ٺاهيو ديڪڪ ڊي 1 ۽ ڊي 2 ، ٻئي ديوتا عناصر جا اشارا ذخيرو ڪن ٿا جيڪي ذيلي-قطار ۾ گهٽ ۾ گهٽ ۽ وڌ ۾ وڌ حصو وٺن ٿا. ديڪ ڊي 1 ۾ واپس آرڊر کان اڳ جي آرڊر ۾ عناصر شامل آهن ۽ ڊي 2 اڳيان کان اڳتي وڌڻ جي آرڊر ۾ عناصر شامل آهي

  1. شروعاتي طور تي متغير رقم 0. جي طور تي ٺاهيو ٻه ڊائيڪس d1 ۽ d2. سائز جي ڪ جي پهرين ذيلي قطار تي غور ڪريو.
  2. جڏهن ته ڪرنٽ جي ذيلي قطار جو موجوده عنصر ڊي 1 جي انڊيڪس ريئر تي موجود عنصر کان وڌيڪ يا برابر آهي ، ديسي ڊي 1 جي پوئين عنصر کي هٽائي ڇڏيو.
  3. جڏهن ته سائز ڪ جي ذيلي قطار جو موجوده عنصر D2 جي انڊيڪس ريئر تي عنصر کان نن orو يا برابر آهي ، ديڪ ڊ 2 جي پوئين عنصر کي هٽائي ڇڏيو.
  4. ٻنهي ديوتا جي پويان هاڻوڪي انڊيڪس کي شامل ڪريو.
  5. رئيڊ ڊيڪ ڊي 1 ذيلي قطار جي وڌ کان وڌ عنصر جو انڊيڪس آهي ۽ ديق ڊي 2 جو ريئر ذيلي قطار جو گهٽ ۾ گهٽ عنصر جو انڊيڪس آهي. وڌ کان وڌ عنصر کي گهٽ ۾ گهٽ شامل ڪريو متغير رقم.
  6. ماپ ڪ جي باقي بچيل ذيلي سرڪش کي ڏسو ، ۽ مرحلن کي 2 کان 5. ورجائي ڏيو. سلائيڊ ونڊو ٽيڪنڪ ۽ صرف اڳوڻي ذيلي قطار ۾ موجود عنصر کي پروسيس نه ڪيو وڃي.
  7. سڀ ذيلي سرشتن کي پار ڪرڻ بعد ، واپسي رقم.

جاوا ڪوڊ کي ڳولڻ لاءِ سڀ کان ننaysن ۽ ڪثرت جي عنصرن جي مقدار جا ڪ

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

سي ++ ڪوڊ ڳولڻ جي نن subن نن maximumن ننaysن ننaysن عناصر جي مقدار کي گهٽ ۾ گهٽ ۽ وڌ ۾ وڌ شي

#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

پيچيدگي تجزيي

وقت جي پيچيدگي = اي (ن)
خلائي پيچيدگي = اي (ن)
جتي ڏنل ڏنل صف ۾ عناصر جو ڪل تعداد.

جيئن اسان قطار استعمال ڪيا آهن جيڪي گھٽڻ ۽ وڌندڙ ترتيب ۾ انگن جي نمائندگي ڪن ٿا ، تنهن ڪري اهي عناصر هڪ ڀيرو محفوظ ڪري رهيا آهن. اهڙي طرح الگورتھم لڪيري وقت رکي ٿو ، ۽ اھڙي طرح جڳھ گھربل پڻ سڌي آھي.