דיפפערענסע עריי | אָנפֿרעג אין דער קייט דערהייַנטיקן אין אָ (1)


שוועריקייט לעוועל שווער
אָפט געבעטן אין אַרסעסיאַם קאָדנאַטיאָן דירעקטי עקספּעדיאַ גוגל קוואַלקאַם
מענגע אָנפֿרעג פּראָבלעם

איר זענט געגעבן אַן ינטעגער מענגע און צוויי טייפּס פון פֿראגן, איינער איז צו לייגן אַ געגעבן נומער אין אַ קייט און די אנדערע צו דרוקן די גאנצע מענגע. דער פּראָבלעם “דיפפערענסע עריי | ראַנגע דערהייַנטיקן אָנפֿרעג אין אָ (1) ”ריקווייערז אונדז צו דורכפירן די קייט דערהייַנטיקונגען אין אָ (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}

דערנאָך מיר וועלן דרוקן די גאנצע מענגע.

די צוויי סעץ פון וואַלועס וועט זיין געדרוקט נאָך דורכפירן די פֿראגן.

דיפפערענסע עריי | אָנפֿרעג אין דער קייט דערהייַנטיקן אין אָ (1)

 

אַלגערידאַם פֿאַר דיפפערענסע עריי

  1. שאַפֿן אַ מענגע פון ​​דער זעלביקער גרייס ווי די געגעבן מענגע.
  2. יניטיאַליזירן דער ערשטער אינדעקס ווי די ערשטער עלעמענט פון די מענגע און לעצט אינדעקס מיט 0. און אַלע אנדערע ינדאַסיז זענען אָנגעפילט מיט דיפעראַנסיז פון קראַנט און פרייַערדיק עלעמענטן.
  3. לייג די ווערט X צו די געגעבן לינקס אינדעקס פון די באשאפן מענגע פֿאַר יעדער דערהייַנטיקן אָנפֿרעג און אַראָפּרעכענען X פון די רעכט אינדעקס פון די באשאפן מענגע.
  4. פֿאַר יעדער דרוק אָנפֿרעג, ערשטער מיר פּלאָמבירן די ינפּוט מענגע מיט די פאָרמולע A [i] = D [i] + A [i-1]. דערנאָך דרוקן די וואַלועס.

דערקלערונג

געגעבן אַ מענגע און אַ נומער און צוויי טייפּס פון פֿראגן. מיר מוזן דורכפירן די צוויי טייפּס פון פֿראגן. מיר וועלן האָבן צוויי נומערן וואָס רעפּראַזענץ אַ קייט צוזאמען מיט אַ נומער 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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (ק) ווו "Q" איז די נומער פון דרוק קוויריז עקסאַקיוטאַד ווי אַ דערהייַנטיקן אָנפֿרעג נעמט אָ (1) צייַט.

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין די מענגע. זינט מיר האָבן באשאפן אַן עקסטרע דיפעראַנסיז, מיר האָבן לינעאַר פּלאַץ קאַמפּלעקסיטי.