Ən az orta ilə verilmiş uzunluğun alt hissəsini tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Accenture Akkolit Amazon Məlumat dəsti Fourkites Paytm Zoho
GeyimBaxılıb 351

Problem bəyanat

“Ən az orta ilə verilmiş uzunluq subarrayını tapın” problemində bir array və bir giriş tam sayı X, ən az / minimum orta ilə X uzunluğunun alt hissəsini tapmaq üçün bir proqram yazın. Ən kiçik ortalamaya sahib subarrayın başlanğıc və bitmə indekslərini yazdırır.

Giriş Formatı

Bir tam dəyər n olan ilk sətir.

Boşluqla ayrılmış n tam ədədi ehtiva edən ikinci sətir.

Tam bir X dəyəri olan üçüncü sətir.

Çıxış formatı

Boşluqla ayrılmış iki tam dəyərdən ibarət ilk və yalnız bir sətir. Birinci tam başlanğıcı, ikinci tam isə ən kiçik ortalamaya sahib subarrayın son indekslərini təmsil edir.

Məhdudiyyətlər

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

misal

5
3 5 1 7 6
2
1 2

Explanation: Subarray indeks 1 ilə 2 arasındadır. 5 və 1 cəminin ən az olduğunu açıq şəkildə görə bilərik.

Ən az orta ilə verilmiş uzunluq subarrayını tapmaq alqoritmi

Bu metodda X ölçülü sürüşmə pəncərə fikrindən istifadə edirik.

1. Ən kiçik ortalamaya sahib subarrayın başlanğıc göstəricisi olan index = 0-ı başlatın

2. İlk X elementinin cəmini tapın və cəm dəyişənində saxlayın

3. Yuxarıdakı cəmi dəyişəninə minimum_sum başlayın

4. Dizini (X + 1) -ci indeksdən serialın sonuna qədər keçin

  • Hər bir arr [i] elementi üçün cəmi = cəmi + arr [i] -arr [iX] hesablayın
  • Cəmi <minimum_sum, onda index = (i-X + 1) və minimum_sum = cəmi edin.

5. İndeksi və indeksini + X -1 alt bölmənin başlanğıcı və sonu olaraq ən az orta ilə çap edin.

Həyata keçirilməsi

Ən az orta ilə verilmiş uzunluq subarrayını tapmaq üçün C ++ proqramı

#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; 
} 

Ən az Orta ilə verilmiş uzunluq subarrayını tapmaq üçün Java proqramı

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

Ən az orta ilə verilmiş uzunluğun alt qatını tapmaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara n verilmiş massivin ölçüsüdür a []. Burada xətti vaxt alan sürüşmə pəncərə konsepsiyasından istifadə edirik.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

Translate »