Хэмжээний асуултуудыг шинэчлэлтгүйгээр


Хэцүү байдлын түвшин Easy
Байнга асуудаг БлэкРок GE Эрүүл мэндийн Moonfrog лабораторууд Синопсис Такси4 Twilio
Array Ларсен ба Тубро Асуулгын асуудал

Асуудлын мэдэгдэл

"Range sum query-г шинэчлэлгүйгээр" гэсэн асуудал танд байна массив of бүхэл тоо ба хүрээ. Асуудлын шийдэл нь өгөгдсөн муж доторх бүх элементүүдийн нийлбэрийг олохыг хүсдэг.

Жишээ нь

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

Тайлбар

(0, 4) мужийн хоорондох бүх тоонуудын нийлбэр нь 40 ба (1, 3) хоорондох бүх тооны нийлбэр нь 24 байна.

Хэмжээний асуултуудыг шинэчлэлтгүйгээр

 

Алгоритм

  1. Өгөгдсөн массивтай ижил хэмжээтэй sumArray массив үүсгэх.
  2. Өгөгдсөн массивыг дайран өнгөрч, sumArray-ийн өмнөх элемент ба өгөгдсөн массивын одоогийн элементийн нийлбэрийг хадгалаад sumArray дотор хадгална.
  3. Асуулга бүрийн хувьд зүүн нь 0-тэй тэнцүү бол sumArray [баруун],
  4. Бусад нь sumArray [баруун] - sumArray [зүүн - 1] буцаана.

Тайлбар

Бид бүхэл тоон массивыг өгсөн бөгөөд асуулга тус бүрт өгөгдсөн муж доторх бүх элементүүдийн нийлбэрийг олохыг хүссэн. Асуулт бүр нь мужын эхлэл ба төгсгөлийн цэг болох мужаас бүрдэнэ. Энэ асуулт нь шинэчлэх лавлагаа оруулахгүй. Энэ нь асуулгын хариуг олж мэдэх явцад ямар нэгэн зүйлийг шинэчлэх шаардлагагүй гэсэн үг юм. Бид өгөгдсөн массивыг 0 индексээс одоогийн индекс хүртэлх бүх элементүүдийн нийлбэр нь баригдсан массивын ith байрлалд байхаар л барих болно. Ийнхүү бүх асуултууд O (1) -ээр шийдэгдэх бөгөөд нэмэлт O (n) зайтай болно.

Бид өөрсдийн үүсгэсэн sumArray-ийг бүтээх болно. Энэ sumArray-д 0-ээс i хүртэлх элементүүдийн нийлбэр sumArray-ийн ith байрлалд хадгалагдах болно. Бид sumArray-ийн өмнөх утга болон өгөгдсөн массивын одоогийн утгыг нэмж, sumArray-ийн одоогийн индекс байрлалд хадгалж байх үед үүнийг тооцоолох болно. Тиймээс хэн нэгэн энэ байрлал дахь бүх тооны нийлбэр хэд болохыг асуухад бид энэ массивын өвөрмөц элемент бүрийн утгыг буцааж өгөх хэрэгтэй.

Бид ямар ч мужаас бүрдсэн асуулга авах бөгөөд хэрэв тухайн мужийн зүүн буюу эхлэлийн цэг 0-тэй тэнцүү бол бид sumArray [right] гэсэн утгыг буцааж өгөх болно. 0-тэй тэнцэхгүй тохиолдолд бид sumArray [баруун] ба sumArray [зүүн-1] -ийн зөрүүг буцаана. Эдгээрт хариулт шаардлагатай болно. Энэ арга нь бидний ашиглах хамгийн хялбар аргуудын нэг юм Динамик програмчлал.

код

Шинэчлэлгүйгээр хүрээний нийлбэр асуулгын C ++ код

#include<iostream>

using namespace std;

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

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

Range sum лавлагааны Java код шинэчлэлтгүйгээр

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N + Q),  Учир нь sumArray-ийг тооцоолохын тулд O (N), дараа нь асуулга тус бүрт O (1) цаг хэрэгтэй болно.

Сансрын нарийн төвөгтэй байдал

Өгөгдсөн хандлагын дагуу бид 0-ээс i хүртэлх элементүүдийн нийлбэрийг хадгалах шинэ sumArray массивыг бүтээсэн болно. Тиймээс энэ хандлага шаардагдана O (N) зай. Гэхдээ бид анхны массивыг өөрчилж болох байсан. Дараа нь сансрын нарийн төвөгтэй байдал тогтмол болж буурах байсан.