Տպեք փոփոխված զանգվածը զանգվածների բազմակի բազմացման գործողություններից հետո  


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Expedia Անվճար լիցքավորում Google Իսկապես Moonfrog լաբորատորիաներ Օլա Քաբս Քվեարկողներ
Դասավորություն Հարցման խնդիր

«Տպել փոփոխված զանգվածը զանգվածի ընդգրկույթի ավելացման բազմակի գործողություններից հետո» խնդրում նշվում է, որ ձեզ տրված է ամբողջ թիվ դասավորություն և տրված են հարցումների '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) ավելացումից հետո ar կլինի {2, 7, 3, 4, 7, 9}

Այժմ ցուցանիշից (3,5) ավելացումը կդառնա {2, 7, 3, 6, 9, 11}

(4,5) ցուցանիշից կրկին աճը կլինի {2, 7, 3, 6, 11, 13}

Այժմ ցուցանիշից (2,4) ավելացումը կդառնա {2, 7, 5, 8, 13, 13}

(1,3) ցուցանիշից կրկին աճը կլինի {2, 9, 7, 10, 13, 13}

 

Տպեք փոփոխված զանգվածը զանգվածների բազմակի բազմացման գործողություններից հետոPin

Gorանգվածի բազմակի գործողությունների ավելացման գործողությունների ալգորիթմ  

  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

Բարդության վերլուծություն  

Timeամանակի բարդություն

 O (q + n) որտեղ «Ն» զանգվածում տարրերի քանակն է և «q” հարցումների քանակն է: Քանի որ մենք օգտագործել ենք նախածանցի գումարման նման մոտեցում, մենք ունենք գծային ժամանակի բարդություն:

Տես նաեւ,
Մետաղադրամների փոփոխության խնդիր

Տիեզերական բարդություն

 O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: