평균이 가장 적은 부분 ​​배열 찾기

난이도 쉽게
자주 묻는 질문 아마존 자본 하나 문 프로그 연구소
배열 수학조회수 80

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

문제 정책

정수 배열과 숫자 k를 제공했습니다. 문제 설명은 최소 평균을 갖는 하위 배열을 찾아야하며, 이는 최소 평균을 갖는 k 요소의 하위 배열을 찾는 것입니다.

arr[] = {12, 34, 20, 30, 24, 45}
k = 3
Sub-Array of [0, 2] has a minimum average.

설명 : 12, 34 및 20은 가능한 모든 하위 배열 중에서 평균이 가장 작은 k 크기의 하위 배열입니다.

arr[] = {42, 20, 15, 26, 10, 33}
k = 3
Sub-Array of [2, 4] has a minimum average.

설명 : 15, 26 및 10은 가능한 모든 하위 배열 중에서 평균이 가장 작은 k 크기의 하위 배열입니다.

평균이 가장 낮은 부분 배열을 찾는 알고리즘

1. Set start and sum to 0.
2. Traverse the array up to the k, and keep storing the sum of all array elements into the sum.
3. Set leastSum to sum.
4. Traverse the array starting from i=k till i<n.
    1. Get the addition of arr[i] - arr[i-k] and update the value of sum and update it into the sum.
    2. Check if the sum is less than leastSum, if true then update the leastSum to sum and set update start to i-k+1.
5. Print start and start+k-1.

설명

평균이 가장 적은 부분 ​​배열 찾기

우리는이 정렬 정수와 숫자 k. 우리의 임무는 크기 k의 가능한 모든 하위 배열 중에서 최소 평균을 찾는 것입니다. n이 k보다 작 으면 최소 평균을 구해야하는 하위 배열의 크기를 통과하면 조건이 있습니다. 해당 배열이 전체 배열의 크기보다 크면 해당 하위 배열 평균을 찾을 수 없습니다. sum 값을 설정하고 0으로 시작합니다. k 값까지 배열을 순회하고 첫 순회를 수행합니다. 배열의 각 요소를 선택하여 합계에 더한 다음 업데이트합니다. 일부 값은 전체 순회 후 합계가되며 이는 하위 배열에있는 모든 값의 합계입니다.

다음으로 할 일은 sum의 값을 leastSum으로 복사하는 것입니다. 크기 k의 모든 하위 배열 중에서 최소 평균을 찾을 것이기 때문입니다. 먼저 처음부터 k 개의 요소까지 배열을 순회하고 그 합계를 leastSum에 저장합니다. 그 후에 각 i에 대해 leastSum에 arr [i] – arr [ik]를 추가합니다. 이것은 우리가 세 번째를 찾고 최소한 확인하는 두 개의 값을 가지고 있다는 것입니다. 그러면 우리가 검사 할 것은 leastSum이 k보다 작은 지, 참이면 leastSum의 값과 start의 값을 i-k + 1로 업데이트하는 것입니다. 이 업데이트 방정식은 k로 시작했기 때문에 출력을 배열의 인덱싱으로 정상으로 유지하기위한 것이므로 조정해야합니다.

순회 후에는 start 값이 있지만 최소 평균을 갖는 하위 배열의 끝 값이 없습니다. start + k-1을 입력하면됩니다. 하위 배열.

평균이 가장 적은 부분 ​​배열을 찾는 코드

C ++ 코드

#include<iostream>

using namespace std;

void getMinimumAvgSubarray(int arr[], int n, int k)
{
    if (n < k)
        return;

    int start = 0;

    int sum = 0;
    for (int i = 0; i < k; i++)
        sum += arr[i];

    int leastSum = sum;

    for (int i = k; i < n; i++)
    {
        sum += arr[i] - arr[i - k];

        if (sum < leastSum)
        {
            leastSum = sum;
            start = (i - k + 1);
        }
    }
    cout << "Sub-array between [" << start << ", "<< start + k - 1 << "] has minimum average";
}
int main()
{
    int arr[] = {12, 34, 20, 30, 24, 45};
    int k = 3;
    int n = sizeof arr / sizeof arr[0];
    getMinimumAvgSubarray(arr, n, k);
    return 0;
}
Sub-array between [0, 2] has minimum average

자바 코드

class MinimumAverageSubArray
{
    public static void getMinimumAvgSubarray(int arr[], int n, int k)
    {
        if (n < k)
            return;

        int start = 0;

        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += arr[i];

        int leastSum = sum;

        for (int i = k; i < n; i++)
        {
            sum += arr[i] - arr[i - k];

            if (sum < leastSum)
            {
                leastSum = sum;
                start = (i - k + 1);
            }
        }
        System.out.println("Subarray between [" +start + ", " + (start + k - 1) +"] has minimum average");
    }
    public static void main(String[] args)
    {
        int arr[] = {12, 34, 20, 30, 24, 45};
        int k = 3;
        getMinimumAvgSubarray(arr, arr.length, k);
    }
}
Subarray between [0, 2] has minimum average

 

복잡성 분석

시간 복잡성  평균이 가장 적은 부분 ​​배열을 찾으려면

O (N) 어디에 "엔" 배열의 요소 수입니다. 여기서 우리는 배열을 한 번만 탐색 했으므로 알고리즘은 선형 시간 복잡도를 갖습니다.

공간 복잡성 평균이 가장 적은 부분 ​​배열을 찾으려면

O (N) 입력을 저장하기 위해 배열을 사용했지만 솔루션은 일정한 추가 공간 만 사용하기 때문입니다.

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