多次数组范围递增操作后打印修改后的数组  


难度级别
经常问 Expedia的 免费收费 谷歌 的确 月蛙实验室 奥拉出租车 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. 将我们创建的数组中的给定值添加到给定范围。 检查给定查询的结束范围是否小于数组的长度。 如果为true,请从我们创建的数组中减小值“ d”。
  4. 遍历给定数组,并通过添加当前值和先前值以及给定数组来更新输出数组。
  5. 打印更新的数组。
参见
总和可被m整除的子集

说明

给定一个 排列 of 整数 和一些查询,每个查询都包含开始和结束范围以及一个给定的值。 我们必须将给定值与从给定范围的起点到终点的所有数字相加。 我们将创建一个查询数组。 该数字中的两个将与每个查询的数组相关联。 我们将创建一个与给定数组长度相同大小的额外数组。 我们将在此阵列上执行操作,然后在给定的阵列上更新这些操作。

现在,我们运行一个循环,直到查询数量达到为止。 我们将通过添加给定值来更新输出数组 d,位于查询的起始索引处。 检查查询的结束值是否小于数组的长度。 如果发现为true,则从输出数组中的先前更新的值中减去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” 是数组中元素的数量。