Пас аз амалиётҳои афзоиши диапазони массив массиви тағирёфтаро чоп кунед


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Expedia FreeCharge Google Ҳақиқатан Озмоишгоҳҳои Moonfrog Ola Cabs Qualities
тартиботи ҳарбӣ Масъалаи пурсиш

Масъалаи "Чоп кардани массиви тағирёфта пас аз амалиётҳои афзоиши диапазони массив" мегӯяд, ки ба шумо ҳамаҷониба асал ва рақамҳои '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} хоҳад буд

 

Пас аз амалиётҳои афзоиши диапазони массив массиви тағирёфтаро чоп кунед

Алгоритми амалҳои афзояндаи диапазони массив

  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 ” шумораи пурсишҳо мебошад. Азбаски мо равишро монанди суммаи префикс истифода кардем, мо мураккабии хаттии вақт дорем.

Мураккабии фазо

 Эй (н) ки дар "Н" шумораи унсурҳои массив аст.