फरक एर्रे | O (१) मा दायरा अपडेट क्वेरी


कठिनाई तह हार्ड
बारम्बार सोधिन्छ आर्सेसियम CodeNation Directi Expedia गुगल Qualcomm
एरे प्रश्न समस्या

तपाईंलाई एक दिइन्छ पूर्णांक array र दुई प्रकारका प्रश्नहरू, एउटा हो दायरामा दिइएको नम्बर थप्न को लागी र अर्को पूरै एरे प्रिन्ट गर्नु हो। समस्या "भिन्नता एरे | O (१) मा दायरा अपडेट क्वेरीले O (१) मा दायरा अपडेट गर्न हामीलाई आवश्यक गर्दछ।

उदाहरणका

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)

स्पष्टीकरण

१० २० र to० मा थपिनेछ, त्यसैले एरे {{०, ,०, २ 10, }० become हुनेछ

त्यसो भए हामी पूरै एर्रे प्रिन्ट गर्नेछौं।

२० लाई 20०, ,० र २ 30 मा थपिनेछ, त्यसैले एरे {{०, ,०, 40 25, }० become हुनेछ

१० २० र to० मा थपिनेछ, त्यसैले एरे {{०, ,०, २ 10, }० become हुनेछ

त्यसोभए हामी फेरि पूरै एर्रे प्रिन्ट गर्नेछौं।

क्वेरीहरू प्रदर्शन गरेपछि दुई सेट मानहरू प्रिन्ट हुनेछन्।

फरक एर्रे | O (१) मा दायरा अपडेट क्वेरी

 

भिन्नता एर्रेको लागि एल्गोरिथ्म

  1. दिइएको एर्रेको समान साइजको एर्रे सिर्जना गर्नुहोस्।
  2. पहिलो अनुक्रमणिका दिइएको एर्रेको पहिलो एलिमेन्टको रूपमा सुरू गर्नुहोस्, र अन्तिम सूचकांक ० साथ। र अन्य सबै सूचकांकहरू हालको र अघिल्लो तत्वको भिन्नताले भरिएका छन्।
  3. प्रत्येक अपडेट क्वेरीको लागि, सिर्जना गरिएको एरेको बायाँ अनुक्रमणिकामा मान X थप्नुहोस् र सिर्जना गरिएको एरेको दायाँ अनुक्रमणिकाबाट X घटाउनुहोस्।
  4. प्रत्येक प्रिन्ट क्वेरीका लागि, पहिले हामी इनपुट एर्रे भार्नेछौं सूत्र A [i] = D [i] + A [i-1] प्रयोग गरेर। तब मानहरू प्रिन्ट गर्नुहोस्।

स्पष्टीकरण

एर्रे र नम्बर र दुई प्रकारका प्रश्नहरू दिइयो। त्यसैले हामीले दुई प्रकारका प्रश्नहरू प्रदर्शन गर्नु पर्छ। हामीसँग दुई नम्बरहरू छन् जुन संख्या एक्ससँग दायरा प्रतिनिधित्व गर्दछ। त्यसैले, हाम्रो कार्य भनेको दायरा बीचको सम्पूर्ण सूचकांकमा नम्बर एक्स थप्नु हो। यसको एउटा विधि भनेको एउटा भोली दृष्टिकोण प्रयोग गर्नु हो। त्यसका लागि, प्रत्येक पटक दिइएको एर्रेपार गर्नुहोस् जब पनि हामी मानहरू अपडेट गर्न आवश्यक पर्दछ।

यहाँ उत्तम समाधानको चर्चा गरिएको छ, जुन एक अतिरिक्त एर्रे सिर्जना गर्ने हो जुन भिन्नता भण्डार गर्दछ। यसैले यसलाई फरक एरे भनिन्छ। पहिले, इनपुट एर्रेको पहिलो एलिमेन्टको रूपमा भिन्नता एरेको पहिलो एलिमेन्ट सुरूवात गर्नुहोस्। त्यसोभए फरक एर्रेको अन्तिम एलिमेन्ट ० लाई तोक्नुहोस्

हामी मान दायराका रूपमा प्राप्त गर्नेछौं, यदि हामीले अपडेट क्वेरी पायौं भने। हामीसँग पनि संख्या प्रदान गरीन्छ। त्यसोभए हामी त्यो नम्बरलाई दायराको बाँया अनुक्रमणिकामा फर्कने छौं। त्यस्तै भिन्नता एर्रेको दाँया अनुक्रमणिकाबाट मान 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

जाभामा भिन्नता एर्रेको लागि कार्यान्वयन

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) जहाँ "क्यू" अपडेट क्वेरी लिने प्रिन्ट क्वेरीहरूको संख्या कार्यान्वयन हुन्छ O (१) समय।

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। किनकि हामीले एक अतिरिक्त भिन्नता एर्रे सिर्जना गरेका छौं, हामीसँग रैखिक स्थान जटिलता छ।