შეცვალეთ შეცვლილი მასივი მასივის მრავალჯერადი დიაპაზონის ზრდის ოპერაციების შემდეგ


Რთული ტური Hard
ხშირად ეკითხებიან Expedia უფასო დატენვა Google ნამდვილად Moonfrog ლაბორატორიები ოლა კაბინები 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) დანამატი გახდება {2, 7, 3, 6, 9, 11}

კვლავ გაზრდა ინდექსიდან (4,5) arr იქნება {2, 7, 3, 6, 11, 13}

ახლა ინდექსის (2,4) დანამატი გახდება {2, 7, 5, 8, 13, 13}

კვლავ გაზრდა ინდექსიდან (1,3) arr იქნება {2, 9, 7, 10, 13, 13}

 

შეცვალეთ შეცვლილი მასივი მასივის მრავალჯერადი დიაპაზონის ზრდის ოპერაციების შემდეგ

მრავალი მასივის დიაპაზონის ზრდის ოპერაციების ალგორითმი

  1. გამოაცხადეთ მასივი, როგორც იგივე ზომა, როგორც მოცემული მასივი.
  2. მასივის გადაკვეთა 0-დან მოთხოვნების საერთო რაოდენობაზე.
  3. მოცემულ დიაპაზონს დაამატეთ მოცემული მნიშვნელობა მასივში, რომელიც ჩვენ შევქმენით. შეამოწმეთ მოცემული მოთხოვნის დასრულების დიაპაზონი ნაკლებია მასივის სიგრძეზე. თუ სიმართლეა, შეამცირეთ მნიშვნელობა ”d” ჩვენს მიერ შექმნილი მასივიდან.
  4. გაიარეთ მოცემული მასივი და განაახლეთ გამომავალი მასივი მიმდინარე და წინა მნიშვნელობებისა და მოცემული მასივის დამატებით.
  5. დაბეჭდეთ განახლებული მასივი.

განმარტება

მოცემული ან მასივი 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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა და ”q ” არის შეკითხვების რაოდენობა. მას შემდეგ, რაც ჩვენ გამოვიყენეთ მიდგომა, როგორც პრეფიქსი ჯამი, გვაქვს ხაზოვანი დროის სირთულე.

სივრცის სირთულე

 O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.