આપેલ બે સortedર્ટ કરેલા એરેના વૈકલ્પિક તત્વોથી બધી શક્ય સortedર્ટ કરેલી એરે બનાવો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ડાયરેક્ટિ કરાત પેપાલ Twilio યાન્ડેક્ષ
અરે રિકર્ઝન

સમસ્યા "આપેલ બે સortedર્ટ કરેલા એરેના વૈકલ્પિક તત્વોથી બધી સંભવિત સોર્ટ એરે બનાવો" જણાવે છે કે ધારો કે તમારી પાસે બે સortedર્ટ કરેલી એરે છે. સમસ્યાનું નિવેદન બધી સંભવિત સોર્ટ કરેલી એરે શોધવા માટે પૂછે છે, જેમ કે સંખ્યાને આપેલ બે જુદી જુદી એરેથી વૈકલ્પિક રીતે ગોઠવવી જોઈએ.

ઉદાહરણ

ArrA[] = {9, 12, 66}
ArrB[] = {10, 15, 25}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

સમજૂતી

બધી વૈકલ્પિક સંખ્યાઓ વિવિધ એરેથી અને સ fromર્ટ કરેલી છે.

આપેલ બે સortedર્ટ કરેલા એરેના વૈકલ્પિક તત્વોથી બધી શક્ય સortedર્ટ કરેલી એરે બનાવો

 

અલ્ગોરિધમ

  1. કદના આઉટપુટ એરેને ઘોષણા કરો મી + એન (બંને એરેની કુલ લંબાઈ).
  2. જો તપાસો boolCondition સાચું છે,
    1. પછી તપાસો કે આઉટપુટ એરેની લંબાઈ 0 ની બરાબર નથી, તો આઉટપુટ એરે છાપો.
      1. એરેને પસાર કરો એઆરએ અને નીચેની તપાસો
        1. જો આઉટપુટ એરેની લંબાઈ 0 હોય તો વર્તમાન ઘટકને આઉટપુટ એરે પર ક copyપિ કરો પછી ફંક્શનને વારંવાર ક callલ કરો.
    2. બાકી જો વર્તમાન એરે એલિમેન્ટ અગાઉના આઉટપુટ એરે એલિમેન્ટ કરતા વધારે હોય, તો પછી એલિમેન્ટની કોપી કરો એઆરએ આઉટપુટ એરેમાં અને વારંવાર ફંક્શનને ક callલ કરો.
  3. બાકી જો બુલકન્ડિશન ખોટી છે, તો પછી પસાર કરો એઆરબી અને તપાસો કે શું હાલનું તત્વ છે એઆરબી આઉટપુટ એરેના વર્તમાન તત્વ કરતા વધારે છે
      1. જો સાચું હોય તો તત્વની નકલ કરો એઆરબી આઉટપુટ એરે પર અને વારંવાર ફંક્શનને ક callલ કરો.

સમજૂતી

“આપેલ બે સortedર્ટ કરેલા એરેના વૈકલ્પિક તત્વોથી બધી સંભવિત સોર્ટ એરે બનાવો” સમસ્યા નીચેની રીતે હલ થઈ શકે છે. અહીં આપણને બે સortedર્ટ થયેલ એરે આપવામાં આવી છે એઆરએ અને એઆરબી. આપેલ બંને એરે સortedર્ટ ક્રમમાં છે. તેથી, આપણે બધા શક્ય શોધવા માટેની જરૂર છે એરે જેનું નિર્માણ સ aર્ટ રીતે કરી શકાય છે. ત્યાં બીજી શરત પણ છે કે આઉટપુટમાં દરેક વૈકલ્પિક તત્વ જુદા જુદા એરેથી આવવા જોઈએ.

બધી સંભવિત આઉટપુટ એરે શોધવા માટે અમે તે ફંક્શનને ફરીથી કહીશું. પછી અમે બુલિયન વેરિયેબલ રાખીશું જે ચૂંટાયેલા તત્વોનો ટ્ર .ક રાખે છે. તે કાં તો તત્ત્વ વર્તમાન એઆરએ અથવા એઆરબીનું છે. જો બુલિયન ચલ સાચું છે, તો પછી આપણે પહેલા એરે એઆરએમાંથી એક તત્વ પસંદ કરીએ છીએ. અન્યથા જો બુલિયન ચલ ખોટો છે, તો પછી આપણે બીજા એરે એઆરબીમાંથી તત્વ પસંદ કરીએ છીએ. જો બુલિયન વેરીએબલ સાચું છે, તો આપણે એરેની લંબાઈ 0 ની બરાબર અથવા 0 કરતા વધારે ન હોય તે તપાસવા જઈશું, તો પછી જ્યારે પણ આપણે આઉટપુટ એરે છાપવા જઈશું.

જો બુલિયન સ્થિતિ સાચી હોય તો આપણે એરે એઆરએ પસાર કરીશું. પછી વર્તમાન એરે એલિમેન્ટને આઉટપુટ એરેમાં ક copyપિ કરો. તે પછી આપણે ફંક્શનને બધી જરૂરી દલીલો પસાર કરીને તેને કursલર્સ કહીએ છીએ. જો બુલિયન સ્થિતિ ખોટી છે. પછી આપણે અમારા આઉટપુટ એરેમાંથી ક copyપિ કરવા અને અપડેટ કરવા માટે એરરબીનો ઉપયોગ કરીએ છીએ. અને દરેક વખતે જ્યારે આઉટપુટ એરેની લંબાઈ 0 હોય, તો પછી એરે છાપો.

કોડ

બધી સંભવિત સ possibleર્ટ કરેલી એરે જનરેટ કરવા માટે સી ++ કોડ

#include<iostream>
using namespace std;

void printArray(int arr[], int n);

void getSortedArr(int ArrA[], int ArrB[], int output[], int i, int j, int m, int n, int len, bool flag)
{
    if (flag)
    {
        if (len)
            printArray(output, len+1);

        for (int k = i; k < m; k++)
        {
            if (!len)
            {
                output[len] = ArrA [k];
                getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len, !flag);
            }
            else
            {
                if (ArrA [k] > output[len])
                {
                    output[len+1] = ArrA [k];
                    getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len+1, !flag);
                }
            }
        }
    }
    else
    {
        for (int l = j; l < n; l++)
        {
            if (ArrB[l] > output[len])
            {
                output[len+1] = ArrB[l];
                getSortedArr(ArrA, ArrB, output, i, l+1, m, n, len+1, !flag);
            }
        }
    }
}

void generate(int ArrA [], int ArrB[], int m, int n)
{
    int output[m+n];
    getSortedArr(ArrA, ArrB, output, 0, 0, m, n, 0, true);
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int ArrA [] = {9, 12, 66};
    int ArrB[] = {10, 15, 25};
    int n = sizeof(ArrA)/sizeof(ArrA [0]);
    int m = sizeof(ArrB)/sizeof(ArrB[0]);
    generate(ArrA, ArrB, n, m);
    return 0;
}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

બધી શક્ય સortedર્ટ કરેલી એરે જનરેટ કરવા માટે જાવા કોડ

class GeneratedSortedArray
{
    public static void getSortedArr(int ArrA[], int ArrB[], int output[], int i, int j, int m, int n, int len, boolean flag)
    {
        if (flag)
        {
            if (len!=0)
                printArray(output, len+1);

            for (int k = i; k < m; k++)
            {
                if (len==0)
                {
                    output[len] = ArrA [k];
                    getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len, !flag);
                }
                else
                {
                    if (ArrA [k] > output[len])
                    {
                        output[len+1] = ArrA [k];
                        getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len+1, !flag);
                    }
                }
            }
        }
        else
        {
            for (int l = j; l < n; l++)
            {
                if (ArrB[l] > output[len])
                {
                    output[len+1] = ArrB[l];
                    getSortedArr(ArrA, ArrB, output, i, l+1, m, n, len+1, !flag);
                }
            }
        }
    }

    public static void generate(int ArrA [], int ArrB[], int m, int n)
    {
        int output[]=new int[m+n];
        getSortedArr(ArrA, ArrB, output, 0, 0, m, n, 0, true);
    }
    
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    
    public static void main(String [] args)
    {
        int ArrA [] = {9, 12, 66};
        int ArrB[] = {10, 15, 25};
        int n = ArrA.length;
        int m = ArrB.length;
        generate(ArrA, ArrB, n, m);
    }
}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (n1 ^ 2 + n2 ^ 2) જ્યાં “એન 1” અને “એન 2” એઆરએ અને એઆરબીની લંબાઈ છે. જ્યારે તત્વો વૈકલ્પિક થાય છે, ત્યારે તે એરા છે [0] <એઆરબી [0] <એઆરએ [1] <એઆરબી [1]… આ કિસ્સામાં, અમારી પાસે કુલ એન 1 ^ 2 + એન 2 ^ 2 સંભવિત સબસિટો હોઈ શકે છે. આમ બહુપદી સમયની જટિલતા.

અવકાશ જટિલતા

ઓ (એન 1 + એન 2) જ્યાં “એન 1” અને “એન 2” એઆરએ અને એઆરબીની લંબાઈ છે. આઉટપુટ એરે દ્વારા જગ્યા લેવામાં આવે છે અને કદ n1 + n2 હોવાથી. જગ્યાની જટિલતા રેખીય છે.