用最小平均找到給定長度的子數組  


難度級別 容易獎學金
經常問 埃森哲 ol石 亞馬遜 事實集 風箏 Paytm 百會
排列

問題陳述  

在“用最小平均數查找給定長度的子數組”問題中,我們給出了 排列 以及一個輸入整數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個元素的總和並將其存儲在sum變量中

3. 將minimum_sum初始化為上述sum變量

4. 從第(X + 1)個索引遍歷數組直到數組末尾

  • 對於每個元素arr [i],計算sum = sum + sum + arr [i] -arr [iX]
  • 如果sum <minimum_sum,則使索引=(i-X + 1),並且minimum_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) 因為我們在這裡不使用任何輔助空間。