दी गई सीमा में समान तत्वों वाले अनुक्रमितों की संख्या  


कठिनाई स्तर मध्यम
में अक्सर पूछा ग्रेओरेन्ज वास्तव में संचालित Pinterest स्नैपडील याहू
ऐरे क्वेरी की समस्या

आपको एक दिया जाता है पूर्णांक सरणी, क्यू क्वेरी, और बाएँ और दाएँ के रूप में एक श्रेणी। "दी गई श्रेणी में समान तत्वों वाले अनुक्रमितों की संख्या" पूर्णांक की गणना की कुल संख्या को इस तरह से पता लगाने के लिए कहती है कि बाएं <= i <सही, ऐसा है कि एi = एज + १.

उदाहरण  

arr[] = {2, 2, 3, 3, 3, 4, 4, 4, 4}
Query = 2
Left = 2, right = 6
Left = 4, right = 8
3
3

व्याख्या

क्वेरी 1 के लिए, जहां बाएं = 2, दाएं = 6

arr[2]=arr[3], arr[3]=arr[4], arr[5]=arr[6]

गिनती 3 है।

क्वेरी 2 के लिए, जहां बाएं = 4, दाएं = 8

arr[5]=arr[6], arr[6]=arr[7], arr[7]=arr[8]

गिनती 3 है।

दी गई सीमा में समान तत्वों वाले अनुक्रमितों की संख्यापिन

 

कलन विधि  

  1. एक सरणी बनाएँ।
  2. सरणी के माध्यम से पार।
  3. यदि वर्तमान सरणी तत्व अगले तत्व के बराबर है, तो निर्मित सरणी का तत्व 1 के बराबर है।
  4. यदि सूचकांक 0 के बराबर नहीं है, तो arrayDummy के वर्तमान सरणी तत्व और अगले सरणी तत्व की arrayDummy [i] में योग करें।
  5. क्वेरी को हल करें, यदि बाईं स्थिति 0 के बराबर है, तो arrayDummy [दाएँ -1] को वापस करें, अन्यथा arrayDummy [दाएँ -1] और arrayDummy [बाएँ -1] का अंतर लौटाएँ।

व्याख्या

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

यह भी देखें
हनोई का Iterative टॉवर

हम शुरू से सरणी तक की लंबाई की तुलना में कम से कम एक के माध्यम से पार करेंगे। फिर हम जांचते हैं कि सरणी का वर्तमान तत्व सरणी के अगले तत्व के बराबर है या नहीं। अगर हालत सही पाई जाती है। तब हम उस मूल्य को वर्तमान सूचकांक '1.' पर चिह्नित करते हैं। हम इसे 1 चिह्नित करेंगे क्योंकि हमें पता चल जाएगा कि आसन्न तत्वों में से कोई भी समान है। फिर प्रत्येक जोड़ी को गिनती 1 के रूप में माना जाता है, अगले जोड़ी को एक तत्व के रूप में पिछली जोड़ी के सामान्य 2 के रूप में गिना जाएगा, और इसी तरह। यदि n जोड़े समान हैं तो n-1 की गिनती होगी। इसके अलावा यदि सूचकांक मान 0. नहीं है। इसका मतलब यह है कि यदि यह पहला तत्व नहीं है ArrayDummy current के तत्व और पिछले तत्व को arrayDummy के वर्तमान सूचकांक में संग्रहीत करें।

दिए गए प्रत्येक प्रश्न के लिए यदि श्रेणी का बायां सूचकांक 0 के बराबर है, तो arrayDummy [दाएं - 1] को वापस करें। और यदि यह 0 नहीं है, तो बस arrayDummy [सही - 1] और arrayDummy [बाएँ - 1] के बीच के अंतर को वापस करें।

कोड  

सी ++ कोड दिए गए रेंज में समान तत्वों के साथ अनुक्रमित की संख्या की गणना करने के लिए

#include <iostream>

using namespace std;

int arrayDummy[100];

void getNumbers(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] == a[i + que
            arrayDummy[i] = 1;

        if (i != 0)
            arrayDummy[i] += arrayDummy[i - 1];
    }
}

int solveQuery(int l, int r)
{
    if (l == 0)
        return arrayDummy[r - 1];
    else
        return arrayDummy[r - 1] - arrayDummy[l - 1];
}

int main()
{
    int arr[] = { 2,2,3,3,3,4,4,4,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    getNumbers(arr, n);

    int left, right;

    left = 2;
    right = 6;

    cout << solveQuery(left, right) << endl;
    left = 4;
    right = 8;
    cout << solveQuery(left, right) << endl;
    return 0;
}
3
3

दिए गए रेंज में समान तत्वों वाले इंडेक्स की संख्या को गिनने के लिए जावा कोड

class IndexElementsEqual
{
    static int arrayDummy[] = new int[1000];

    public static void getNumbers(int arr[], int n)
    {
        for (int i = 0; i < n-1; i++)
        {
            if (arr[i] == arr[i + 1])
                arrayDummy[i] = 1;

            if (i != 0)
                arrayDummy[i] += arrayDummy[i - 1];
        }
    }
    public static int solveQuery(int left, int right)
    {
        if (left == 0)
            return arrayDummy[right - 1];
        else
            return arrayDummy[right - 1] - arrayDummy[left - 1];
    }
    public static void main(String args[])
    {
        int arr[] = {2,2,3,3,3,4,4,4,4};
        int n = arr.length;

        getNumbers(arr, n);

        int left, right;

        left = 2;
        right = 6;

        System.out.println(solveQuery(left, right));
        left = 4;
        right = 8;
        System.out.println(solveQuery(left, right));
    }
}
3
3

जटिलता विश्लेषण  

समय जटिलता

 ओ (1) हर क्वेरी के लिए और पर) प्री-कंप्यूटिंग के लिए।

यह भी देखें
उच्च या निम्न संख्या का अनुमान लगाएं

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

पर) जहां "N" सरणी में तत्वों की संख्या है। यह जगह arrayDummy के निर्माण के लिए आवश्यक है।