複数の配列範囲インクリメント操作後に変更された配列を出力します


難易度 ハード
よく聞かれる エクスペディア 費用無料 Googleポリシー 確かに ムーンフロッグラボ オラキャブ Qualtrics
配列 クエリの問題

「複数の配列範囲インクリメント操作の後に変更された配列を出力する」という問題は、 整数 配列 および「q」個のクエリが与えられます。 XNUMXつの整数値「d」も指定されます。 各クエリには、開始値と終了値のXNUMXつの整数が含まれています。 問題ステートメントは、指定された範囲内の配列内のすべての値を値「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. 更新された配列を出力します。

説明

与えられた 配列 of 整数 いくつかのクエリでは、各クエリには開始範囲と終了範囲、および指定された値が含まれます。 指定された範囲の開始点から終了点までのすべての数値に、指定された値を合計する必要があります。 クエリの配列を作成します。 番号のうちのXNUMXつは、クエリの各配列に関連付けられます。 指定された配列の長さと同じサイズの追加の配列を作成します。 この配列で操作を実行してから、指定された配列でこれらの操作を更新します。

ここで、クエリの数までループを実行します。 指定された値を追加して出力配列を更新します d、クエリの開始インデックス。 クエリの終了値が配列の長さよりも短いかどうかを確認してください。 trueの場合、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) where 「n」 は配列内の要素の数であり、「q」 クエリの数です。 プレフィックス合計のようなアプローチを使用したため、線形の時間計算量があります。

スペースの複雑さ

 O(N) where 「n」 配列の要素数です。