최소 평균으로 주어진 길이의 부분 배열 구하기

난이도 쉽게
자주 묻는 질문 Accenture 수행자 아마존 팩트 셋 포카이트 Paytm 조호 (Zoho)
배열조회수 400

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

문제 정책

“최소 평균으로 주어진 길이의 부분 배열 찾기”문제에서 우리는 정렬 입력 정수 X를 입력합니다. 최소 / 최소 평균으로 길이 X의 부분 배열을 찾는 프로그램을 작성합니다. 평균이 가장 적은 부분 ​​배열의 시작 및 끝 인덱스를 인쇄합니다.

입력 형식

정수 값 n을 포함하는 첫 번째 줄입니다.

공백으로 구분 된 n 개의 정수를 포함하는 두 번째 줄.

정수 값 X를 포함하는 세 번째 줄입니다.

출력 형식

공백으로 구분 된 두 개의 정수 값을 포함하는 첫 번째 및 유일한 행입니다. 첫 번째 정수는 시작을 나타내고 두 번째 정수는 평균이 가장 적은 하위 배열의 끝 인덱스를 나타냅니다.

제약

  • 1 <= N <= 10 ^ 5
  • 1 <= a [i] <= 10 ^ 9
  • 1 <= X <= N

5
3 5 1 7 6
2
1 2

설명 : 하위 배열은 인덱스 1과 2 사이에 있습니다. 5와 1의 합이 가장 작다는 것을 분명히 알 수 있습니다.

최소 평균으로 주어진 길이의 부분 배열을 찾는 알고리즘

이 방법에서는 크기 X의 슬라이딩 윈도우 아이디어를 사용합니다.

1. 평균이 가장 적은 부분 ​​배열의 시작 인덱스 인 인덱스 = 0 초기화

2. 첫 번째 X 요소의 합계를 찾아서 합계 변수에 저장

3. least_sum을 위의 sum 변수로 초기화하십시오.

4. (X + 1) 번째 인덱스부터 배열 끝까지 배열 탐색

  • 모든 요소 arr [i]에 대해 sum = sum + arr [i] -arr [iX] 계산
  • sum <least_sum이면 index = (i-X + 1) 및 least_sum = sum으로 만듭니다.

5. 인덱스와 인덱스 + X -1을 최소 평균으로 하위 배열의 시작과 끝으로 인쇄합니다.

실시

최소 평균으로 주어진 길이의 하위 배열을 찾는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
  int k;
  cin>>k;
  if(n>=k)
  {
      int ans = 0; 
    	int sum = 0; 
    	for(int i=0;i<k;i++) 
    	{
    		sum+=a[i];
    	}
    	int min_sum=sum; 
    	for (int i=k;i<n;i++) 
    	{ 
    		sum+=a[i]-a[i-k]; 
    		if(sum<min_sum) 
    		{ 
    			min_sum = sum; 
    			ans = (i-k+1); 
    		} 
    	} 
    	cout<<ans<<" "<<ans+k-1<<endl;
  }
  else
  {
     cout<<-1<<endl;
  }
  return 0; 
} 

최소 평균으로 주어진 길이의 하위 배열을 찾는 Java 프로그램

import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        int a[]= new int[n];
        for(int i=0;i<n;i++)
        {
            a[i]=sr.nextInt();
        }
        int k = sr.nextInt();
        if(n>=k)
        {
            int ans = 0; 
            int sum = 0; 
            for(int i=0;i<k;i++) 
            {
                    sum+=a[i];
            }
            int min_sum=sum; 
            for (int i=k;i<n;i++) 
            { 
                    sum+=a[i]-a[i-k]; 
                    if(sum<min_sum) 
                    { 
                            min_sum = sum; 
                            ans = (i-k+1); 
                    } 
            } 
            System.out.println(ans +" "+(ans+k-1));
        }
        else
        {
            System.out.println(-1);
        } 
    }
}
10
1 4 3 6 23 76 43 1 2 89
4
0 3

최소 평균으로 주어진 길이의 부분 배열을 찾기위한 복잡성 분석

시간 복잡성

O (N) 어디에 n 주어진 배열의 크기입니다. ㅏ[]. 여기서는 선형 시간이 걸리는 슬라이딩 윈도우의 개념을 사용합니다.

공간 복잡성

O (1) 여기서는 보조 공간을 사용하지 않기 때문입니다.

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