ค้นหา Subarray ของความยาวที่กำหนดด้วยค่าเฉลี่ยน้อยที่สุด  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคเซนเจอร์ แอคโคไลท์ อเมซอน ข้อเท็จจริง โฟร์ไคต์ Paytm Zoho
แถว

คำชี้แจงปัญหา  

ในโจทย์“ ค้นหา Subarray ของความยาวที่กำหนดโดยมีค่าเฉลี่ยน้อยที่สุด” เราได้ระบุไฟล์ แถว และจำนวนเต็มอินพุต X เขียนโปรแกรมเพื่อค้นหา subarray ของความยาว X ที่มีค่าเฉลี่ยน้อยที่สุด / ต่ำสุด พิมพ์ดัชนีเริ่มต้นและสิ้นสุดของ subarray ซึ่งมีค่าเฉลี่ยน้อยที่สุด

รูปแบบการป้อนข้อมูล  

บรรทัดแรกที่มีค่าจำนวนเต็ม n

บรรทัดที่สองประกอบด้วยจำนวนเต็มที่คั่นด้วยช่องว่าง n จำนวนเต็ม

บรรทัดที่สามมีค่าจำนวนเต็ม X

รูปแบบผลลัพธ์  

บรรทัดแรกและบรรทัดเดียวที่มีค่าจำนวนเต็มสองค่าโดยคั่นด้วยช่องว่าง จำนวนเต็มที่แรกแสดงถึงการเริ่มต้นและจำนวนเต็มที่สองแสดงถึงดัชนีสิ้นสุดของ subarray ซึ่งมีค่าเฉลี่ยน้อยที่สุด

ข้อ จำกัด  

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

ตัวอย่าง  

5
3 5 1 7 6
2
1 2

คำอธิบาย: subarray อยู่ระหว่างดัชนี 1 และ 2 เราสามารถเห็นได้อย่างชัดเจนว่าผลรวมของ 5 และ 1 เป็นค่าน้อยที่สุด

อัลกอริทึมเพื่อค้นหา Subarray ของความยาวที่กำหนดโดยมีค่าเฉลี่ยน้อยที่สุด  

ในวิธีนี้เราใช้แนวคิดของหน้าต่างบานเลื่อนขนาด X

1. เริ่มต้นดัชนี = 0 ซึ่งเป็นดัชนีเริ่มต้นของ subarray ที่มีค่าเฉลี่ยน้อยที่สุด

ดูสิ่งนี้ด้วย
หาระยะห่างต่ำสุดระหว่างตัวเลขสองตัว

2. ค้นหาผลรวมขององค์ประกอบ X แรกและเก็บไว้ในตัวแปรผลรวม

3. เริ่มต้น less_sum กับตัวแปร sum ข้างต้น

4. สำรวจอาร์เรย์จากดัชนี (X + 1) th จนถึงจุดสิ้นสุดของอาร์เรย์

  • สำหรับทุกองค์ประกอบ arr [i] ให้คำนวณ sum = sum + arr [i] -arr [iX]
  • ถ้า sum <less_sum ให้สร้าง index = (i-X + 1) และ less_sum = sum

5. พิมพ์ดัชนีและดัชนี + X -1 เป็นจุดเริ่มต้นและจุดสิ้นสุดของ subarray โดยมีค่าเฉลี่ยน้อยที่สุด

การดำเนินงาน  

โปรแกรม C ++ เพื่อค้นหา Subarray ของความยาวที่กำหนดด้วยค่าเฉลี่ยน้อยที่สุด

#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 เพื่อค้นหา Subarray ของความยาวที่กำหนดโดยมีค่าเฉลี่ยน้อยที่สุด

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

การวิเคราะห์ความซับซ้อนเพื่อค้นหา Subarray ของความยาวที่กำหนดด้วยค่าเฉลี่ยน้อยที่สุด  

ความซับซ้อนของเวลา

O (n) ที่ไหน n คือขนาดของอาร์เรย์ที่กำหนด ก []. ที่นี่เราใช้แนวคิดของหน้าต่างบานเลื่อนซึ่งใช้เวลาเชิงเส้น

ความซับซ้อนของอวกาศ

O (1) เพราะเราไม่ได้ใช้พื้นที่เสริมตรงนี้