크기가 k 인 모든 부분 배열의 최소 및 최대 요소의 합

난이도 하드
자주 묻는 질문 ByteDance 자본 하나 쿠폰 Dunia 데이터 브릭 구글 Twilio Yandex 주차
배열 슬라이딩 윈도우조회수 116

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“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은 주어진 배열의 총 요소 수입니다.

크기가 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 인 모든 하위 배열의 최소 및 최대 요소의 합계를 찾는 C ++ 코드

#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)

여기서 시간 복잡도는 각 하위 배열의 문제를 독립적으로 해결하기 때문에 다항식입니다. 최대 및 최소에 대한 두 개의 변수 만 저장했기 때문에 필요한 공간은 일정합니다.

최적의 접근 방식

두 개 만들기 데케 d1 및 d2, 두 deques 모두 하위 배열의 최소 및 최대에 기여할 수있는 요소의 인덱스를 저장합니다. Deque d1은 앞쪽에서 뒤쪽으로 내림차순으로 요소를 포함하고 d2는 앞쪽에서 뒤쪽으로 오름차순으로 요소를 포함합니다.

  1. 변수 합계를 0으로 초기화합니다. 두 개의 deques d1과 d2를 만듭니다. 크기 k의 첫 번째 하위 배열을 고려하십시오.
  2. 크기가 k 인 하위 배열의 현재 요소가 d1의 인덱스 뒷면에있는 요소보다 크거나 같지만 Deque d1의 뒷면 요소를 제거합니다.
  3. 크기가 k 인 하위 배열의 현재 요소가 d2의 인덱스 후면에있는 요소보다 작거나 같지만 Deque d2의 후면 요소를 제거합니다.
  4. 두 deques 뒤에 현재 색인을 추가합니다.
  5. deque d1의 후면은 서브 어레이의 최대 요소 인덱스이고 deque d2의 후면은 서브 어레이의 최소 요소 인덱스입니다. 최대 및 최소 요소의 합계를 변수 합계에 더합니다.
  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 인 모든 하위 배열의 최소 및 최대 요소의 합계를 찾는 C ++ 코드

#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은 주어진 배열의 총 요소 수입니다.

감소 및 증가 순서로 숫자를 나타내는 큐를 사용 했으므로 요소를 한 번 저장합니다. 따라서 알고리즘은 선형 시간이 걸리므로 필요한 공간도 선형입니다.

균열 시스템 설계 인터뷰
Translate »