ค่าเฉลี่ยของช่วงในอาร์เรย์


ระดับความยาก กลาง
ถามบ่อยใน จังหวะอินเดีย Expedia ฟรีค่าธรรมเนียม สีเทาOrange Roblox Snapchat Snapdeal ไทม์อินเทอร์เน็ต Yandex
แถว ปัญหาการสืบค้น

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

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

ตัวอย่าง

array[] = {2, 5, 1, 6, 7, 8}

Query: {(1, 4), (0,2), (4,5)}
4 2 7

คำอธิบาย

(1,4) ดังนั้นค่าเฉลี่ยของ 5,1,6,7 ซึ่งก็คือ 4

(0,2) ดังนั้นค่าเฉลี่ยของ 2,5,1 ซึ่งก็คือ 2

(4,5) ดังนั้นค่าเฉลี่ยของ 7,8 ซึ่งก็คือ 7

ค่าเฉลี่ยของช่วงในอาร์เรย์

 

ขั้นตอนวิธี

  1. สร้างอาร์เรย์ PreMeanSum และเริ่มต้นค่าแรกเป็นค่าของอาร์เรย์ที่กำหนด
  2. สำรวจอาร์เรย์จาก 1 และเก็บผลรวมของค่าก่อนหน้าของ PreMeanSum และค่าปัจจุบันของอาร์เรย์ที่กำหนดให้เป็นค่าปัจจุบันของอาร์เรย์ PreMeanSum
  3. รับตำแหน่งซ้ายและขวาของแบบสอบถามและตรวจสอบว่าตำแหน่งด้านซ้ายที่กำหนดเป็น 0 หรือไม่ถ้าเป็นจริงให้ส่งกลับผลหารของ PreMeanSum [right] / right + 1
  4. ส่งคืนค่าของ PreMeanSum [ขวา] -PreMeanSum [ซ้าย - 1] / ขวา - ซ้าย +1

คำอธิบาย

เราได้กำหนดอาร์เรย์จำนวนเต็มและจำนวนคิวรี ดังนั้นเราจึงขอให้ส่งคืนค่าพื้นของค่าเฉลี่ยของตัวเลขที่มาในช่วงที่กำหนด ดังนั้นวิธีง่ายๆที่สามารถปฏิบัติตามเช่นสำหรับแต่ละแบบสอบถามเราจะข้ามอาร์เรย์จากจุดเริ่มต้นของช่วงไปยังจุดสิ้นสุดของช่วง และเก็บผลรวมของค่าทั้งหมดเป็นค่าเฉพาะ สมมติว่าเราต้องหาค่าเฉลี่ยของ (0, i) ดังนั้น arr [i] เราจะต้องสรุปค่าทั้งหมดจากอาร์เรย์ศูนย์หนึ่งค่าตามค่าที่กำหนด จากนั้นเราจะส่งคืนผลหารของผลรวมนั้นและจำนวนค่าทั้งหมดซึ่งเป็นผลรวม

แต่ข้อเสียอย่างหนึ่งคือเราต้องสำรวจช่วงที่กำหนดสำหรับแต่ละคิวรีถ้าเรามี n คิวรี มันจะเคลื่อนที่ตามจำนวนเวลา n แต่วิธีการที่เราใช้มันจะส่งกลับคำตอบของแต่ละแบบสอบถามในเวลาคงที่หลังจากที่เราสร้างอาร์เรย์หนึ่งครั้ง

เราจะสร้างอาร์เรย์เนื่องจากเราได้ประกาศอาร์เรย์ PreMeanSum อาร์เรย์ จากนั้นเริ่มต้นองค์ประกอบแรกของอาร์เรย์ PreMeanSum เป็นค่าแรกของอาร์เรย์ที่กำหนด เราจะสำรวจอาร์เรย์จากหนึ่งไปยังความยาวของอาร์เรย์จุดประสงค์ของการทำคือเราต้องเก็บผลรวมของค่าที่อยู่ติดกันสองค่ากับค่าปัจจุบันในขณะที่ข้าม นั่นเป็นเหตุผลที่เราคัดลอกค่าแรกนั้นและเริ่มจาก 1 เราจะได้รับช่วงเป็นจุดเริ่มต้นและจุดสิ้นสุด หลังจากนั้นเราจะตรวจสอบว่าค่าทางซ้ายที่ระบุเท่ากับ 0 หรือไม่ถ้าเป็นจริงจากนั้นส่งคืนการหารของ PreMeanSum [ขวา] / ขวา + 1 เพียงแค่รวม / จำนวนค่าทั้งหมด มิฉะนั้นเราจะส่งคืนการหารความแตกต่างของ PreMeanSum [ขวา] -PreMeanSum [ซ้าย -1] และขวา - ซ้าย + 1 นั่นจะเป็นคำตอบที่ต้องการ

รหัส

รหัส C ++ เพื่อค้นหาค่าเฉลี่ยของช่วงในอาร์เรย์

#include<iostream>
#include<math.h>

#define MAX 1000005
using namespace std;

int PreMeanSum[MAX];

void buildPreMean(int arr[], int n)
{
    PreMeanSum[0] = arr[0];
    for (int i = 1; i < n; i++)
        PreMeanSum[i] = PreMeanSum[i - 1] + arr[i];
}

int getMeanInRange(int l, int r)
{
    if (l == 0)
        return floor(PreMeanSum[r] / (r + 1));

    return floor( (PreMeanSum[r] - PreMeanSum[l - 1]) / (r - l + 1));
}

int main()
{

    int arr[] = {2,5,1,6,7,8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    buildPreMean(arr, n);
    cout << getMeanInRange(1, 4) << endl;
    cout << getMeanInRange(0, 2) << endl;
    cout << getMeanInRange(4, 5) << endl;
    return 0;
}
4
2
7

โค้ด Java เพื่อค้นหาค่าเฉลี่ยของช่วงในอาร์เรย์

class MeanInRange
{
    public static final int MAX = 1000005;

    static int PreMeanSum[] = new int[MAX];

    static void buildPreMean(int arr[], int n)
    {
        PreMeanSum[0] = arr[0];
        for (int i = 1; i < n; i++)
            PreMeanSum[i] = PreMeanSum[i - 1] + arr[i];
    }

    static int getMeanInRange(int l, int r)
    {
        if (l == 0)
            return (int)Math.floor(PreMeanSum[r] / (r + 1));

        return (int)Math.floor((PreMeanSum[r] -
                                PreMeanSum[l - 1]) / (r - l + 1));
    }

    public static void main(String[] args)
    {
        int arr[] = {2,5,1,6,7,8 };
        int n = arr.length;
        buildPreMean(arr, n);
        System.out.println(getMeanInRange(1, 4));
        System.out.println(getMeanInRange(0, 2));
        System.out.println(getMeanInRange(4, 5));
    }
}
4
2
7

การวิเคราะห์ความซับซ้อน

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

O (n + q) ที่ไหน "Q" คือจำนวนแบบสอบถามที่ต้องดำเนินการตามค่าเฉลี่ยที่สามารถคำนวณได้ O (1) ความซับซ้อนของเวลา O (n) ต้องใช้เวลาในการคำนวณล่วงหน้า PreMeanSum

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

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์