Печать измененного массива после нескольких операций увеличения диапазона массива


Сложный уровень Жесткий
Часто спрашивают в Expedia Свободный заряд Google В самом деле Лаборатория лунной лягушки Ола Кабс Qualtrics
массив Проблема с запросом

В задаче «Печать измененного массива после нескольких операций увеличения диапазона массива» указано, что вам дается целое массив и даны «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

Анализ сложности

Сложность времени

 О (д + п) в котором «Н» - количество элементов в массиве, а «q ” количество запросов. Поскольку мы использовали такой подход, как сумма префиксов, мы имеем линейную временную сложность.

Космическая сложность

 О (п) в котором «Н» это количество элементов в массиве.