लगातार समय सीमा एक सरणी पर ऑपरेशन जोड़ें


कठिनाई स्तर आसान
में अक्सर पूछा कोडेशन डीई शॉ डायरेक्टी 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. जांचें कि क्या मान सही अंतिम सरणी सूचकांक के बराबर नहीं है, फिर दिए गए मूल्य को सरणी के दाईं ओर + 1 स्थिति में घटाएं और इसे स्वयं स्टोर करें।
  2. सरणी को प्रिंट करने से पहले सरणी को सरणी के माध्यम से अनुप्रस्थ के रूप में अपडेट करें और पिछले और वर्तमान मूल्य को जोड़ दें और इसे सरणी मान में संग्रहीत करें।
  3. अपडेशन के बाद, परिणामी सरणी को प्रिंट करें।

लगातार समय सीमा के लिए स्पष्टीकरण एक सरणी पर ऑपरेशन जोड़ें

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

प्रत्येक दिए गए क्वेरी के लिए, बाएं और दाएं, हम दिए गए मान को दाईं ओर के बाएं इंडेक्स में जोड़ने जा रहे हैं, केवल बाएं इंडेक्स पर याद रखें। और सही मूल्य के लिए, हम यह जांचने जा रहे हैं कि क्या मान अधिकार सरणी के अंतिम सूचकांक के बराबर नहीं है, यदि दी गई स्थिति संतुष्ट है तो हम दिए गए मूल्य सूचकांक को अपडेट करने जा रहे हैं, हम दिए गए मूल्य को घटा देंगे सरणी का सही सूचकांक और इसे सरणी के सही स्थिति सूचकांक में संग्रहीत करें। प्रत्येक क्वेरी के लिए, हम ये ऑपरेशन करने जा रहे हैं।

अब हमें ऐरे को प्रिंट करना है, लेकिन इससे पहले, हम सभी वैल्यू को अपडेट करने जा रहे हैं, हमने जो अतिरिक्त ऑपरेशन किया है, हमें उसे अपडेट करना होगा। इसलिए सरणी को ट्रेस करके, वर्तमान मान और दिए गए सरणी के पिछले मान को जोड़कर और इसे सरणी की वर्तमान स्थिति में संग्रहीत करके सरणी को अपडेट करें। उसके बाद, हम सरणी को प्रिंट करने जा रहे हैं।

कोड

लगातार समय सीमा के लिए 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

लगातार समय सीमा के लिए जावा में कार्यान्वयन एक सरणी पर ऑपरेशन जोड़ते हैं

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) जहां "एन" सरणी में तत्वों की संख्या और है 'क्यू' प्रश्नों की संख्या है। क्योंकि हमने बाईं इंडेक्स पर वैल्यू बढ़ाई है और एरे की सीमा में मौजूद होने पर राइट + 1 इंडेक्स में वैल्यू घटा दी है।

अंतरिक्ष जटिलता

पर) जहां "एन" सरणी में तत्वों की संख्या है।