差異數組| O(1)中的範圍更新查詢  


難度級別
經常問 弓箭 編碼國家 指令 Expedia的 谷歌 高通公司
排列 查詢問題

給你一個 整數 排列 兩種查詢,一種是在範圍內添加給定的數字,另一種是打印整個數組。 問題“差異數組| O(1)中的範圍更新查詢”要求我們在O(1)中執行範圍更新。

例  

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

解釋

10將添加到20和30,因此該數組將變為{30,40,25,50}

然後,我們將打印整個數組。

將20加到30、40和25,因此數組將變為{50,60,45,50}

10將添加到45和50,因此該數組將變為{50,60,75,80}

然後,我們將再次打印整個數組。

執行查詢後,將打印兩組值。

差異數組| O(1)中的範圍更新查詢

 

差分數組算法  

  1. 創建一個與給定數組大小相同的數組。
  2. 將第一個索引初始化為給定數組的第一個元素,將最後一個索引初始化為0。所有其他索引都填充有當前元素和上一個元素的差。
  3. 對於每個更新查詢,將值X添加到創建的數組的給定左索引中,然後從創建的數組的右索引中減去X。
  4. 對於每個打印查詢,首先我們使用公式A [i] = D [i] + A [i-1]填充輸入數組。 然後打印值。
也可以看看
給定兩個未排序的數組,找到所有總和為x的對

解釋  

給定一個數組和一個數字以及兩種查詢類型。 因此,我們必須執行兩種類型的查詢。 我們將有兩個數字代表一個範圍以及一個數字X。因此,我們的任務是將數字X添加到給定範圍之間的所有索引中。 其中一種方法可能是使用幼稚的方法。 為此,每當需要更新值時,遍歷給定的數組。

這裡討論一個更好的解決方案,即創建一個額外的數組來存儲差異。 這就是為什麼它被稱為差異數組的原因。 首先,將差異數組的第一個元素初始化為輸入數組的第一個元素。 然後將差異數組的最後一個元素分配為0。之後,我們將遍歷該數組並將當前值和先前值的差異存儲在差異數組中的當前索引處。

如果獲得更新查詢,我們將獲得這些值作為範圍。 除了我們,我們還提供了一些號碼。 然後,我們將在差值數組的範圍的左索引處添加該數字。 類似地,從差數組的右索引中減去值X。 為了打印數組,我們將遍歷該數組,對於零索引值,我們將更新給定數組的值作為創建的數組,否則我們將獲取創建的數組與給定數組的先前值的和。打印特定索引的值。

也可以看看
給定範圍內具有相等元素的索引數

推薦碼  

C ++中差異數組的實現

#include<iostream>

using namespace std;

void buildArray(int arr[], int dummyArray[], int n)
{
    dummyArray[0] = arr[0];
    dummyArray[n] = 0;
    for (int i = 1; i < n; i++)
        dummyArray[i] = arr[i] - arr[i - 1];
}

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

void printArray(int arr[], int dummyArray[], int n)
{
    for (int i = 0; i <n; i++)
    {

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}
30 40 25 50
50 60 75 80

Java中差異數組的實現

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}
30 40 25 50
50 60 75 80

複雜度分析  

時間複雜度

O(q) 哪裡 “Q” 是更新查詢執行時執行的打印查詢的數量 O(1) 時間。

也可以看看
具有不同元素的子數組

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 由於我們創建了一個額外的差分數組,因此我們具有線性的空間複雜度。