આપેલ શ્રેણીમાં સમાન તત્વો સાથે અનુક્રમણિકાઓની સંખ્યા


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ગ્રેઓરેંજ ખરેખર ઓપેરા Pinterest સ્નેપડીલ યાહૂ
અરે ક્વેરી સમસ્યા

તમે એક આપવામાં આવે છે પૂર્ણાંક એરે, q ક્વેરીઝ અને ડાબી અને જમણી શ્રેણી. "આપેલ શ્રેણીમાં સમાન તત્વો સાથે અનુક્રમણિકાઓની સંખ્યા" કહે છે કે પૂર્ણાંકોની કુલ સંખ્યાની સંખ્યાને એવી રીતે શોધવા માટે કે <= 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 અને તેથી વધુ. પછી અમે મહત્તમ કદની એરે બનાવીએ છીએ. અમે એક ફંક્શન બનાવ્યું છે જે અનુક્રમણિકાની ગણતરી કરે છે જે આપેલ સ્થિતિને સંતોષે છે. સ્થિતિ એ છે કે બે સંલગ્ન તત્વો એકબીજા સાથે સમાન છે.

આપણે એરેથી શરૂ કરીને એરેની લંબાઈથી ઓછી એક તરફ પસાર કરીશું. પછી આપણે એરેનું વર્તમાન તત્વ એરેના આગામી તત્વ સાથે સમાન છે કે નહીં તે તપાસીએ છીએ. જો સ્થિતિ સાચી હોવાનું જાણવા મળે છે. પછી આપણે તે મૂલ્યને વર્તમાન અનુક્રમણિકામાં 'થી' ચિહ્નિત કરીએ છીએ. આપણે આને ચિહ્નિત કરીશું કારણ કે આપણે નજીકના તત્વોમાંના કોઈપણ સમાન છે કે નહીં તે જાણીશું. પછી દરેક જોડીને ગણતરી 1 તરીકે ગણવામાં આવે છે, આગલી જોડી એક તત્વ સાથેની પહેલાની જોડી 1 તરીકે ગણવામાં આવશે, અને તેથી વધુ. જો n જોડીઓ સમાન હોય તો ત્યાં n-1 ની ગણતરી થશે. જો અનુક્રમણિકા મૂલ્ય 2 ન હોય તો પણ તેનો અર્થ એ કે જ્યારે તે પ્રથમ તત્વ ન હોય તો ટ્ર traવર્સિંગ કરતી વખતે. એરે ડમી વર્તમાનના તત્વ અને અગાઉના તત્વનો સરવાળો એરેના ડમીના વર્તમાન અનુક્રમણિકામાં સંગ્રહિત કરો.

આપેલ દરેક ક્વેરી માટે જો શ્રેણીનો ડાબું અનુક્રમણિકા 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) દરેક ક્વેરી માટે અને ઓ (એન) પ્રી-કમ્પ્યુટિંગ માટે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. આ જગ્યા એરે ડમી બનાવટ માટે જરૂરી છે.