दिलेल्या श्रेणीतील समान घटकांसह अनुक्रमणिकांची संख्या  


अडचण पातळी मध्यम
वारंवार विचारले ग्रेऑरेंज खरंच ऑपेरा करा Snapdeal याहू
अरे क्वेरी समस्या

आपण एक दिले जाते पूर्णांक अॅरे, क्यू क्वेरी आणि डावी आणि उजवीकडील श्रेणी. “दिलेल्या श्रेणीतील समान घटकांसह अनुक्रमणिकांची संख्या” असे म्हणतात की पूर्णा i्यांची एकूण संख्या अशा प्रकारे सोडल्यास <= i <उजवीकडे, जसे कीi = एj + 1.

उदाहरण  

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 च्या बरोबरीचा नसेल तर अ‍ॅरेडी डमीच्या वर्तमान अ‍ॅरे घटकांचा आणि पुढील अ‍ॅरे घटकाचा अ‍ॅरे डमी [i] मध्ये संचयित करा.
  5. क्वेरीचे निराकरण करा, जर डावी स्थिती 0 च्या बरोबरीने असेल तर अ‍ॅरेडी डमी [उजवे -1] परत करा, अन्यथा अ‍ॅरेडी डमी [उजवे -1] आणि अ‍ॅरे डमी [डावे -1] मधील फरक परत करा.

स्पष्टीकरण

आम्हाला एक दिले जाते पूर्णांक अ‍ॅरे आणि डावी बाजू आणि उजवीकडे एक श्रेणी. आम्हाला जवळपासचे घटक एकमेकांच्या बरोबरीने अशा प्रकारे निर्देशांकांची संख्या शोधण्यास सांगितले जाते. आम्हाला दोन भिन्न निर्देशांक असलेली दोन समान जोडलेली तत्त्वे आढळल्यास, नंतर 1 मोजा आणि इतकेच. मग आम्ही जास्तीत जास्त आकाराचा अ‍ॅरे बनवू. आम्ही अनुक्रमणिकेची गणना करणारी एक फंक्शन तयार केली आहे जी दिलेली अट पूर्ण करते. अट अशी आहे की दोन समीप घटक एकमेकांच्या बरोबरीचे आहेत.

हे सुद्धा पहा
हॅनाइचा Iterative टॉवर

Startरेच्या लांबीपेक्षा कमी असलेल्या आरमेतून आपण अ‍ॅरेमधून पुढे जाऊ. तर अ‍ॅरेचा चालू घटक अ‍ॅरेच्या पुढील घटकाइतका आहे की नाही हे तपासून बघू. जर स्थिती सत्य असल्याचे आढळले तर. मग आम्ही ते मूल्य सध्याच्या निर्देशांकाला 'टू 1' म्हणून चिन्हांकित करतो. आम्ही हे 1 चिन्हांकित करीत आहोत कारण आपल्याला जवळचे कोणतेही घटक समान आहेत का ते कळेल. मग प्रत्येक जोडी गणना 1 मानली जाईल, पुढील जोडी मागील घटकासारख्या एका घटकासह 2 मोजली जाईल, आणि असेच. एन जोड्या समान असल्यास एन -1 ची गणना होईल. तसेच जर निर्देशांक मूल्य 0 नसेल तर याचा अर्थ असा की जेव्हा ते प्रथम घटक नसल्यास ट्रॅव्हर्सिंग करतात. अ‍ॅरेडम्मीच्या वर्तमान निर्देशांकात अ‍ॅरेडम्मी करंटचा घटक आणि मागील घटकाची बेरीज संचयित करा.

दिलेल्या श्रेणीतील डावे अनुक्रमणिका 0 च्या समान असल्यास दिलेल्या क्वेरीसाठी अ‍ॅरेडम्मी [उजवीकडे - 1] परत करा. नाहीतर 0 नसेल तर अ‍ॅरेडम्मी [उजवे - 1] आणि अ‍ॅरे डमी [डावे - 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) प्रत्येक क्वेरीसाठी आणि O (n) प्री-संगणनासाठी.

हे सुद्धा पहा
अंदाज क्रमांक उच्च किंवा निम्न II

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. अ‍ॅरेडमी तयार करण्यासाठी ही जागा आवश्यक आहे.