在陣列上進行恆定時間範圍的添加操作


難度級別 容易獎學金
經常問 編碼國家 指令 Expedia的 谷歌
排列 動態編程

您給了 整數 排列 最初,它被初始化為0並給出了一個範圍。 任務是在數組範圍內添加給定數字並打印結果數組。

arr[] = {0, 0, 0, 0, 0}

Query: {(0, 2, 50), (3, 4, 20), (1, 3, 30)}
50 80 80 50 20

解釋

將50添加到數組中的0到2,數組將變為 {50、50、50、0、0}

將20添加到數組中的3到4,數組將變為 {50、50、50、20、20}

將30添加到數組中的1到3,數組將變為 {50、80、80、80、20}

在陣列上進行恆定時間範圍的添加操作

 

算法

  1. 對於範圍的每個查詢,請遵循以下步驟。
    1. 將給定值添加到數組的左索引,並將其存儲到自身。
    2. 檢查right值是否不等於最後一個數組索引,然後在數組的right + 1位置減去給定值並將其存儲到自身。
  2. 在打印數組之前,更新數組以遍歷數組,並添加前一個和當前值並將其存儲到數組值本身。
  3. 更新後,打印結果數組。

數組上恆定時間範圍添加操作的說明

給定一個整數數組和要添加的數字。 我們還提供了一系列查詢。 它包含範圍的起點(如左)和範圍的終點(如右)。 我們被要求將給定範圍內的給定數字添加到所有可能的整數中。 然後最後打印結果數組。 為此,我們將以一種非常修改的方式執行加法運算。 我們將在數組的左右+1位置使用給定值填充數組索引值,並在打印之前更新該數組。

對於每個給定的查詢(左右),我們將給定的值添加到右邊的左索引處,僅記住在左索引處。 對於正確的值,我們將檢查right的值是否不等於數組的最後一個索引,如果滿足給定條件,則將更新給定的值索引,我們將從中減去給定的值。數組的正確索引,並將其存儲到數組本身的正確位置索引。 對於每個查詢,我們將執行這些操作。

現在我們必須打印數組,但是在此之前,我們將更新所有值,我們執行的加法運算,我們需要更新它。 因此,通過遍歷數組並將當前值與給定數組的先前值相加,將其存儲到數組的當前位置,從而更新數組。 然後,我們將打印數組。

推薦碼

在C ++中實現對數組進行恆定時間範圍添加操作

#include<iostream>

using namespace std;

void update(int arr[], int N)
{
    for (int i = 1; i < N; i++)
        arr[i] += arr[i - 1];
}

void addOperation(int arr[], int N, int left, int right, int value)
{
    arr[left] += value;
    if (right != N - 1)
        arr[right + 1] -= value;
}

void printArray(int arr[], int N)
{
    update(arr, N);
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int N = 5;

    int arr[N] = {0};

    addOperation(arr, N, 0, 2, 50);
    addOperation(arr, N, 3, 4, 20);
    addOperation(arr, N, 1, 3, 30);

    printArray(arr, N);
    return 0;
}
50 80 80 50 20

Java的實現,用於在陣列上進行恆定時間範圍的添加操作

class AddOperation
{
    static void update(int arr[], int N)
    {
        for (int i = 1; i < N; i++)
            arr[i] += arr[i - 1];
    }
    static void addOperation(int arr[], int N, int left, int right, int value)
    {
        arr[left] += value;
        if (right != N - 1)
            arr[right + 1] -= value;
    }
    static void printArray(int arr[], int N)
    {
        update(arr, N);

        for (int i = 0; i < N; i++)
            System.out.print(""+arr[i]+" ");
        System.out.print("\n");
    }
    public static void main (String[] args)
    {
        int N = 5;

        int arr[] = new int[N];

        addOperation(arr, N, 0, 2, 50);
        addOperation(arr, N, 3, 4, 20);
        addOperation(arr, N, 1, 3, 30);
        printArray(arr, N);
    }
}
50 80 80 50 20

複雜度分析

時間複雜度

O(N + Q) 哪裡 “ N” 是數組中元素的數量,並且 “ Q” 是查詢數。 因為我們已經將左索引處的值增加了,而將右+1索引處的值減小了(如果它存在於數組的邊界中)。

空間複雜度

上) 哪裡 “ N” 是數組中元素的數量。