ವ್ಯತ್ಯಾಸ ಅರೇ | 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 become ಆಗುತ್ತದೆ

ನಂತರ ನಾವು ಇಡೀ ಶ್ರೇಣಿಯನ್ನು ಮುದ್ರಿಸುತ್ತೇವೆ.

20 ಅನ್ನು 30, 40 ಮತ್ತು 25 ಕ್ಕೆ ಸೇರಿಸಲಾಗುತ್ತದೆ, ಆದ್ದರಿಂದ ರಚನೆಯು {50, 60, 45, 50 become ಆಗುತ್ತದೆ

10 ಅನ್ನು 45 ಮತ್ತು 50 ಕ್ಕೆ ಸೇರಿಸಲಾಗುತ್ತದೆ, ಆದ್ದರಿಂದ ರಚನೆಯು {50, 60, 75, 80 become ಆಗುತ್ತದೆ

ನಂತರ ಮತ್ತೆ ನಾವು ಇಡೀ ಶ್ರೇಣಿಯನ್ನು ಮುದ್ರಿಸುತ್ತೇವೆ.

ಪ್ರಶ್ನೆಗಳನ್ನು ನಿರ್ವಹಿಸಿದ ನಂತರ ಎರಡು ಸೆಟ್ ಮೌಲ್ಯಗಳನ್ನು ಮುದ್ರಿಸಲಾಗುತ್ತದೆ.

ವ್ಯತ್ಯಾಸ ಅರೇ | O (1) ನಲ್ಲಿ ಶ್ರೇಣಿ ನವೀಕರಣ ಪ್ರಶ್ನೆ

 

ವ್ಯತ್ಯಾಸ ಅರೇಗಾಗಿ ಅಲ್ಗಾರಿದಮ್

  1. ಕೊಟ್ಟಿರುವ ರಚನೆಯಂತೆಯೇ ಒಂದೇ ಗಾತ್ರದ ಶ್ರೇಣಿಯನ್ನು ರಚಿಸಿ.
  2. ಮೊದಲ ಸೂಚ್ಯಂಕವನ್ನು ರಚನೆಯ ಮೊದಲ ಅಂಶದಂತೆ ಪ್ರಾರಂಭಿಸಿ, ಮತ್ತು ಕೊನೆಯ ಸೂಚ್ಯಂಕವನ್ನು 0 ರೊಂದಿಗೆ ಪ್ರಾರಂಭಿಸಿ. ಮತ್ತು ಎಲ್ಲಾ ಇತರ ಸೂಚ್ಯಂಕಗಳು ಪ್ರಸ್ತುತ ಮತ್ತು ಹಿಂದಿನ ಅಂಶದ ವ್ಯತ್ಯಾಸದಿಂದ ತುಂಬಿರುತ್ತವೆ.
  3. ಪ್ರತಿ ನವೀಕರಣ ಪ್ರಶ್ನೆಗೆ, ರಚಿಸಿದ ರಚನೆಯ ಎಡ ಸೂಚ್ಯಂಕಕ್ಕೆ X ಮೌಲ್ಯವನ್ನು ಸೇರಿಸಿ ಮತ್ತು ರಚಿಸಿದ ರಚನೆಯ ಬಲ ಸೂಚ್ಯಂಕದಿಂದ X ಅನ್ನು ಕಳೆಯಿರಿ.
  4. ಪ್ರತಿ ಮುದ್ರಣ ಪ್ರಶ್ನೆಗೆ, ಮೊದಲು ನಾವು A [i] = D [i] + A [i-1] ಸೂತ್ರವನ್ನು ಬಳಸಿಕೊಂಡು ಇನ್ಪುಟ್ ಶ್ರೇಣಿಯನ್ನು ತುಂಬುತ್ತೇವೆ. ನಂತರ ಮೌಲ್ಯಗಳನ್ನು ಮುದ್ರಿಸಿ.

ವಿವರಣೆ

ಒಂದು ಶ್ರೇಣಿ ಮತ್ತು ಸಂಖ್ಯೆ ಮತ್ತು ಎರಡು ರೀತಿಯ ಪ್ರಶ್ನೆಗಳನ್ನು ನೀಡಲಾಗಿದೆ. ಆದ್ದರಿಂದ ನಾವು ಎರಡು ರೀತಿಯ ಪ್ರಶ್ನೆಗಳನ್ನು ನಿರ್ವಹಿಸಬೇಕಾಗಿದೆ. ನಾವು X ಸಂಖ್ಯೆಯ ಜೊತೆಗೆ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಎರಡು ಸಂಖ್ಯೆಗಳನ್ನು ಹೊಂದಿರುತ್ತೇವೆ. ಆದ್ದರಿಂದ, ಕೊಟ್ಟಿರುವ ಶ್ರೇಣಿಯ ನಡುವಿನ ಎಲ್ಲಾ ಸೂಚ್ಯಂಕಗಳಿಗೆ X ಸಂಖ್ಯೆಯನ್ನು ಸೇರಿಸುವುದು ನಮ್ಮ ಕಾರ್ಯವಾಗಿದೆ. ನಿಷ್ಕಪಟ ವಿಧಾನವನ್ನು ಬಳಸುವುದು ಒಂದು ವಿಧಾನವಾಗಿದೆ. ಅದಕ್ಕಾಗಿ, ನಾವು ಮೌಲ್ಯಗಳನ್ನು ನವೀಕರಿಸಬೇಕಾದಾಗಲೆಲ್ಲಾ ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗಿರಿ.

ಉತ್ತಮ ಪರಿಹಾರವನ್ನು ಇಲ್ಲಿ ಚರ್ಚಿಸಲಾಗಿದೆ, ಇದು ವ್ಯತ್ಯಾಸವನ್ನು ಸಂಗ್ರಹಿಸುವ ಹೆಚ್ಚುವರಿ ಶ್ರೇಣಿಯನ್ನು ರಚಿಸುವುದು. ಅದಕ್ಕಾಗಿಯೇ ಇದನ್ನು ವ್ಯತ್ಯಾಸ ಶ್ರೇಣಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತಿದೆ. ಮೊದಲಿಗೆ, ವ್ಯತ್ಯಾಸ ರಚನೆಯ ಮೊದಲ ಅಂಶವನ್ನು ಇನ್ಪುಟ್ ರಚನೆಯ ಮೊದಲ ಅಂಶವಾಗಿ ಪ್ರಾರಂಭಿಸಿ. ನಂತರ ವ್ಯತ್ಯಾಸ ಶ್ರೇಣಿಯ ಕೊನೆಯ ಅಂಶವನ್ನು 0 ಗೆ ನಿಗದಿಪಡಿಸಿ. ಅದರ ನಂತರ, ನಾವು ರಚನೆಯ ಮೂಲಕ ಸಂಚರಿಸಲು ಹೋಗುತ್ತೇವೆ ಮತ್ತು ಪ್ರಸ್ತುತ ಮೌಲ್ಯ ಮತ್ತು ಹಿಂದಿನ ಮೌಲ್ಯದ ವ್ಯತ್ಯಾಸವನ್ನು ಪ್ರಸ್ತುತ ಶ್ರೇಣಿಯಲ್ಲಿ ವ್ಯತ್ಯಾಸ ಶ್ರೇಣಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ.

ನಾವು ನವೀಕರಣ ಪ್ರಶ್ನೆಯನ್ನು ಪಡೆದರೆ ನಾವು ಮೌಲ್ಯಗಳನ್ನು ಶ್ರೇಣಿಯಾಗಿ ಪಡೆಯುತ್ತೇವೆ. ನಮ್ಮೊಂದಿಗೆ ಒಂದು ಸಂಖ್ಯೆಯನ್ನು ಸಹ ನೀಡಲಾಗುತ್ತದೆ. ನಂತರ ನಾವು ಆ ಸಂಖ್ಯೆಯನ್ನು ಶ್ರೇಣಿಯ ಎಡ ಸೂಚ್ಯಂಕದಲ್ಲಿ ವ್ಯತ್ಯಾಸ ಶ್ರೇಣಿಯಲ್ಲಿ ಸೇರಿಸಲಿದ್ದೇವೆ. ಅದೇ ರೀತಿ ವ್ಯತ್ಯಾಸ ಶ್ರೇಣಿಯ ಬಲ ಸೂಚ್ಯಂಕದಿಂದ X ಮೌಲ್ಯವನ್ನು ಕಳೆಯಿರಿ. ವ್ಯೂಹವನ್ನು ಮುದ್ರಿಸಲು ನಾವು ರಚನೆಯ ಮೂಲಕ ಸಂಚರಿಸುತ್ತೇವೆ ಮತ್ತು ಶೂನ್ಯ ಸೂಚ್ಯಂಕ ಮೌಲ್ಯಕ್ಕಾಗಿ ನಾವು ಕೊಟ್ಟಿರುವ ರಚನೆಯ ಮೌಲ್ಯವನ್ನು ನಾವು ರಚಿಸಿದ ರಚನೆಯಂತೆ ನವೀಕರಿಸುತ್ತೇವೆ, ಇಲ್ಲದಿದ್ದರೆ ನಾವು ರಚಿಸಿದ ರಚನೆಯ ಮೊತ್ತ ಮತ್ತು ಕೊಟ್ಟಿರುವ ರಚನೆಯ ಹಿಂದಿನ ಮೌಲ್ಯವನ್ನು ಪಡೆಯುತ್ತೇವೆ ಮತ್ತು ನಿರ್ದಿಷ್ಟ ಸೂಚ್ಯಂಕಕ್ಕಾಗಿ ಆ ಮೌಲ್ಯವನ್ನು ಮುದ್ರಿಸಿ.

ಕೋಡ್

ವ್ಯತ್ಯಾಸ ಅರೇಗಾಗಿ ಸಿ ++ ನಲ್ಲಿ ಅನುಷ್ಠಾನ

#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

ಡಿಫರೆನ್ಸ್ ಅರೇಗಾಗಿ ಜಾವಾದಲ್ಲಿ ಅನುಷ್ಠಾನ

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) ಸಮಯ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ನಾವು ಹೆಚ್ಚುವರಿ ವ್ಯತ್ಯಾಸ ಶ್ರೇಣಿಯನ್ನು ರಚಿಸಿದ್ದರಿಂದ, ನಮಗೆ ರೇಖೀಯ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆ ಇದೆ.