k 길이의 최대 평균 부분 배열 찾기

난이도 쉽게
자주 묻는 질문 아마존
배열조회수 53

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

문제 정책

당신은 주어진 정렬 정수와 숫자 k. 문제 설명은 k 길이의 최대 평균 부분 배열을 찾도록 요청합니다. 하위 배열은 원래 배열 요소의 연속 블록으로 구성된 배열 일뿐입니다.

arr[] = {1,3,12,34,76,10}
[2, 4]

설명 : 인덱스 2에서 인덱스 4로 시작하는 배열은 최대 평균을 보유합니다. 따라서 [2,4]는 길이 2의 최대 평균 부분 배열입니다.

arr[] = {1,-2,8,3,-6,9}
[1, 3]

설명 : 인덱스 1에서 인덱스 3까지 시작하는 배열은 최대 평균을 보유합니다.

 

k 길이의 최대 평균 부분 배열을 찾는 알고리즘

1. Declare a currentSum.
2. Set the currentSum to arr[0].
3. Traverse the array from i=1 to less than the length of n.
  Store and update the addition of currentSum and arr[i] into the currentSum.
4. Set maximumSum to currentSum.
5. Set END to k-1.
6. Traverse the array from i=k to k to i < n.
7. Set sum to sum + arr[i] - arr[i - k].
  Check if the sum is greater than maximumSum.
    1. Set sum to maximumSum.
    2. Set END to i.
8. Return END – k + 1.

 

설명

정수 배열과 숫자 k가 주어집니다. 우리는 크기 k의 부분 배열의 최대 평균을 찾아야합니다. 이것은 우리가 찾은 평균이 배열의 연속 된 k 개 여야 함을 의미합니다. 따라서 하위 배열 내에서 k 개의 평균을 구할 것입니다. 다음과 같은 경우 조건을 선언했습니다. k 보다 큰 n,. 참이면 -1을 반환합니다. 즉, k 값이 n 값보다 크면 k의 유효한 값이 없다는 것을 의미합니다. k가 배열의 크기보다 클 수는 없습니다.

우리는 이미 현재 합계. 주어진 배열의 첫 번째 값을 currentSum에 복사합니다. 그런 다음 이미 currentSum 값에 대한 작업을 수행 했으므로 인덱스 1에서 배열을 탐색합니다. 그래서 우리는 배열을 순회하고 currentSum과 arr [i]의 이전 요소의 합을 얻어서 currentSum에 저장할 것입니다.

우리는 가치를 설정했습니다 최대합 currentSum의 (k-1) 번째 위치에, END는 k-1에. k 번째 위치에서 배열의 마지막 요소까지 배열을 순회합니다. 우리는 차이를 얻을 것입니다 arr [i]arr [i – k] 그리고 우리는 그것을 합계의 값에 더하고 그것을 합계에 저장합니다. 또한 우리는 위치 k에서 시작한 음의 값에 대해 걱정할 필요가 없습니다. 그래서 우리는 거기에서 어떤 차이도 얻지 못할 것입니다. 합계가 maximumSum보다 크면 합계 값과 종료 값의 maximumSum을 i로 설정합니다. 배열의 길이에 도달 할 때까지 동일한 프로세스를 반복 할 것입니다. 그런 다음 우리는 돌아올 것입니다 끝 – k + 1.

이 기술은 슬라이딩 윈도우 기술이라고도합니다.

k 길이의 최대 평균 부분 배열 찾기

 

k 길이의 최대 평균 부분 배열을 찾는 코드

C ++ 코드

#include<iostream>
using namespace std;
int getMaxAvgSubArray(int arr[], int n, int k)
{
    if (k > n)
        return -1;
    int currentSum;
    currentSum = arr[0];
    for (int i = 1; i < n; i++)
        currentSum = currentSum + arr[i];
    int maximumSum = currentSum;
    int END = k - 1;
    for (int i = k; i < n; i++)
    {
        currentSum = currentSum + arr[i] - arr[i-k];
        if (currentSum > maximumSum)
        {
            maximumSum = currentSum;
            END = i;
        }
    }
    return END - k + 1;
}
int main()
{
    int arr[] = {1,3,12,34,76,10};
    int k = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    int start=getMaxAvgSubArray(arr, n, k);
    cout<<"Maximum average subarray: ["<< start<<" "<< (start + k - 1)<<"]";
    return 0;
}
Maximum average subarray: [2 4]

자바 코드

class MaximumAverageSubarray
{
    public static int getMaxAvgSubArray(int []arr,int n, int k)
    {
        if (k > n)
            return -1;

        int currentSum = arr[0];

        for (int i = 1; i < k; i++)
            currentSum = currentSum + arr[i];

        int maximumSum = currentSum;
        int END = k - 1;

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

            if (currentSum > maximumSum)
            {
                maximumSum = currentSum;
                END = i;
            }
        }
        return END - k + 1;
    }
    public static void main (String[] args)
    {
        int []arr = {1,3,12,34,76,10};
        int k = 3;
        int n = arr.length;
        int start=getMaxAvgSubArray(arr, n, k);
        System.out.println("Maximum average subarray: ["+start+" "+ (start + k - 1)+"]");
    }
}
Maximum average subarray: [2 4]

복잡성 분석

k 길이의 최대 평균 부분 배열을 찾기위한 시간 복잡성

배열을 한 번 통과 했으므로 선형 시간 복잡성이 있습니다. O (N) 어디에 "엔" 배열의 요소 수입니다.

k 길이의 최대 평균 부분 배열을 찾기위한 공간 복잡성

입력을 저장하기 위해 배열을 사용했기 때문에 선형 공간 복잡성이 있습니다. O (N) 어디에 "엔" 배열의 요소 수입니다.

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