Олон тооны массивыг нэмэгдүүлэх үйлдлийн дараа өөрчлөгдсөн массивыг хэвлэх  


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Expedia Үнэгүй цэнэглэх Google-ийн Үнэндээ Moonfrog лабораторууд Ola Cabs Qualtrics
Array Асуулгын асуудал

"Олон тооны массивын хэмжээг нэмэгдүүлэх үйлдлүүдийн дараа өөрчлөгдсөн массивыг хэвлэх" гэсэн асуудал нь танд өгөгдсөн болохыг харуулж байна бүхэл тоо массив ба 'q' асуултын тоог өгсөн болно. Нэг "d" бүхэл тоон утгыг бас өгнө. Асуулга бүр нь эхлэх ба төгсгөлийн утга гэсэн хоёр бүхэл тоонуудыг агуулна. Асуудлын шийдэл нь өгөгдсөн муж доторх массив дахь бүх утгыг "d" утгаар нэмэгдүүлэхийг олж мэдэхийг хүсдэг. Өөрчлөгдсөн массивыг хэвлэх.

Жишээ нь  

arr[] = {2, 5, 1, 4, 7, 9}
Query: (1, 2), (3, 5), (4, 5), (2, 4), (1, 3)
d = 2
2 9 7 10 13 13

Тайлбар

Индекс (1,2) -ээс өссөний дараа arr нь {2, 7, 3, 4, 7, 9} болно.

Одоо (3,5) arr индексээс нэмэгдэх нь {2, 7, 3, 6, 9, 11} болно.

(4,5) arr индексээс дахин өсөх нь {2, 7, 3, 6, 11, 13} болно.

Одоо (2,4) arr индексээс нэмэгдэх нь {2, 7, 5, 8, 13, 13} болно.

(1,3) arr индексээс дахин өсөх нь {2, 9, 7, 10, 13, 13} болно.

 

Олон тооны массивыг нэмэгдүүлэх үйлдлийн дараа өөрчлөгдсөн массивыг хэвлэхPin

Олон тооны массивыг нэмэгдүүлэх үйлдлийн алгоритм  

  1. Массивыг өгөгдсөн массивтай ижил хэмжээгээр зарлана уу.
  2. Массивыг 0-ээс нийт асуулгын тоогоор дамжина.
  3. Бидний үүсгэсэн массив дахь өгөгдсөн утгыг өгөгдсөн мужид нэмнэ. Өгөгдсөн асуулгын төгсгөлийн хүрээ нь массивын уртаас бага эсэхийг шалгана уу. Хэрэв үнэн бол бидний үүсгэсэн массиваас “d” утгыг бууруулна уу.
  4. Өгөгдсөн массивыг дайран өнгөрч, гаралтын массивыг одоогийн ба өмнөх утгууд болон өгөгдсөн массивыг нэмж шинэчлээрэй.
  5. Шинэчлэгдсэн массивыг хэвлэх.
мөн үзнэ үү
Нийлбэрийг m-д хуваах дэд хэсэг

Тайлбар

Өгсөн массив of бүхэл тоо мөн хэдэн тооны асуулга, асуулга бүр нь эхлэх ба дуусах хүрээ ба өгөгдсөн утгыг агуулна. Бид өгөгдсөн мужийн эхлэх цэгээс төгсгөл цэг хүртэлх бүх тоонд өгөгдсөн утгыг нэмэх ёстой. Бид олон тооны асуулга үүсгэх болно. Дугаарын хоёр нь асуулга тус бүрийн массивтай холбоотой байх болно. Бид өгөгдсөн массивын урттай ижил хэмжээтэй нэмэлт массив үүсгэх болно. Бид энэ массив дээрх үйлдлүүдийг гүйцэтгэж дараа нь эдгээр массив дээрх үйлдлүүдийг шинэчлэх болно.

Одоо бид асуулгын тоо хүртэл давталт ажиллуулдаг. Бид өгөгдсөн утгыг нэмж гаралтын массивыг шинэчлэх болно d, асуулга эхлэх индекс дээр. Асуулгын төгсгөлийн утга нь массивын уртаас бага эсэхийг шалгана уу. Хэрэв үнэн бол үнэн гэж тогтоогдвол гаралтын массив дахь өмнө нь шинэчлэгдсэн утгаас d-ийг бууруулна уу. Энэ нь бид хүрээ ба утгуудаас гарахгүй байх явдал юм.

Одоо бид өгөгдсөн массивын эхний байрлалыг гаралтын массивын эхний байрлал болгон шинэчлэх гэж байна. Бид нийлбэр (эсвэл гаралтын) массивын өмнөх утга ба одоогийн утгыг дайран өнгөрөх болно. Тиймээс бид эхний утгыг аль хэдийн шинэчилсэн бөгөөд одоо гаралтын массивын эхний байрлалаас эцсээ хүртэл туулна. Бид өмнөх болон одоогийн утгыг нэмж гаралтын массивт хадгалах болно. Дараа нь тухайн утгыг өгөгдсөн массивын байрлал руу хуулж байгаад хуулж ав. Өөрчлөгдсөн массивыг хэвлэх.

мөн үзнэ үү
Бүх сөрөг тоонуудыг эхлэл рүү шилжүүлж, эерэг орон зайг тогтмол нэмэлт зайгаар дуусгах

код  

Олон тооны массивыг нэмэгдүүлэх үйлдлийн дараа өөрчлөгдсөн массивыг хэвлэх C ++ код

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

struct query
{
    int start, end;
};

void incrementByD(int arr[], struct query q_arr[],int n, int m, int d)
{
    int sum[n];
    memset(sum, 0, sizeof(sum));

    for (int i = 0; i < m; i++)
    {
        sum[q_arr[i].start] += d;

        if ((q_arr[i].end + 1) < n)
            sum[q_arr[i].end + 1] -= d;
    }
    arr[0] += sum[0];
    for (int i = 1; i < n; i++)
    {
        sum[i] += sum[i - 1];
        arr[i] += sum[i];
    }
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = {2, 5, 1, 4, 7, 9};
    struct query q_arr[] = { { 1, 2 }, { 3, 5 },  {4,5 },
        { 2, 4 }, { 1, 3 }
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = sizeof(q_arr) / sizeof(q_arr[0]);

    int d = 2;

    cout << "Original Array:\n";
    printArray(arr, n);

    incrementByD(arr, q_arr, n, m, d);

    cout << "\nModified Array:\n";
    printArray(arr, n);

    return 0;
}
Original Array:
2 5 1 4 7 9
Modified Array:
2 9 7 10 13 13

Олон тооны массивыг нэмэгдүүлэх үйл ажиллагааны дараа өөрчлөгдсөн массивыг хэвлэх Java код

class modifiedArray
{
    static class query
    {
        int start, end;

        query(int start, int end)
        {
            this.start = start;
            this.end = end;
        }
    }

    public static void incrementByD(int[] arr, query[] q_arr, int n, int m, int d)
    {
        int[] sum = new int[n];

        for (int i = 0; i < m; i++)
        {
            sum[q_arr[i].start] += d;

            if ((q_arr[i].end + 1) < n)
                sum[q_arr[i].end + 1] -= d;
        }
        arr[0] += sum[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] += sum[i - 1];
            arr[i] += sum[i];
        }
    }

    public static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }

    public static void main(String[] args)
    {
        int[] arr = { 2, 5, 1, 4, 7, 9};
        query[] q_arr = {new query(1, 2),new query(3,5),new query(4, 5),
                  new query(2, 4),new query(1, 3)
        };

        int n = arr.length;
        int m = q_arr.length;
        int d = 2;
        System.out.println("Original Array:");
        printArray(arr, n);

        incrementByD(arr, q_arr, n, m, d);
        System.out.println("\nModified Array:");
        printArray(arr, n);
    }
}
Original Array:
2 5 1 4 7 9
Modified Array:
2 9 7 10 13 13

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

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

 O (q + n) хаана "N" нь массив дахь элементийн тоо ба “q ” гэдэг нь асуулгын тоо юм. Бид угтварын нийлбэр шиг хандлагыг ашигласан тул цаг хугацааны шугаман нарийн төвөгтэй байдалтай байна.

мөн үзнэ үү
Зоос солих асуудал

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

 O (N) хаана "N" массив дахь элементүүдийн тоо юм.