Генеришите све могуће сортиране низове из алтернативних елемената два дата сортирана низа


Ниво тешкоће Средњи
Често питани у Дирецти карат ПаиПал Твилио иандек
Ред Рекурзије

Проблем „Генериши све могуће сортиране низове из алтернативних елемената два дата сортирана низа“ наводи да претпостављамо да имате два сортирана низа. Изјава о проблему тражи да се сазнају сви могући разврстани низови, тако да би се број требао распоредити наизменично из два дата различита низа.

Пример

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

Објашњење

Сви алтернативни бројеви су из различитих низова и сортирани.

Генеришите све могуће сортиране низове из алтернативних елемената два дата сортирана низа

 

Алгоритам

  1. Декларишите излазни низ величине м + н (укупна дужина оба поља).
  2. Провери да ли је боолЦондитион тачно је,
    1. Затим проверите да ли дужина излазног низа није једнака 0, а затим одштампајте излазни низ.
      1. Пређите низ АррА и проверите следеће
        1. Ако је дужина излазног низа 0 онда копирајте тренутни елемент у излазни низ, а затим рекурзивно позовите функцију.
    2. Иначе ако је тренутни елемент низа већи од претходног излазног елемента низа, онда копирајте елемент из АррА у излазни низ и рекурзивно позовите функцију.
  3. Иначе ако је боолЦондитион нетачно, пређите преко АррБ и проверите да ли је тренутни елемент АррБ је већи од тренутног елемента излазног низа
      1. Ако је тачно, копирајте елемент из АррБ на излазни низ и рекурзивно позвати функцију.

Објашњење

Проблем „Генериши све могуће сортиране низове из алтернативних елемената два дата сортирана низа“ може се решити на следећи начин. Овде су дата два сортирана низа АррА АррБ. Оба дата низа су поређана. Дакле, морамо сазнати све могуће низови који се могу конструисати на сортиран начин. Такође постоји још један услов да сваки алтернативни елемент у излазу долази из различитих низова.

Рекурзивно ћемо позвати ту функцију да бисмо сазнали све могуће излазне низове. Затим чувамо логичку променљиву која прати елементе који се бирају. То је или елемент из тренутне АррА или АррБ. Ако је логичка променљива тачна, тада бирамо елемент из првог низа АррА. у супротном ако је логичка променљива нетачна, тада бирамо елемент из другог низа АррБ. Ако је логичка променљива тачна, проверићемо да ли дужина низа није једнака 0 или је једноставно већа од 0, тада ћемо сваки пут исписати излазни низ.

Прећи ћемо низ АррА ако је логички услов тачан. Затим копирајте тренутни елемент низа у излазни низ. Тада рекурзивно позивамо функцију прослеђујући јој све потребне аргументе. Ако је логички услов нетачан. Затим користимо АррБ за копирање и ажурирање нашег излазног низа. И сваки пут када је дужина излазног низа 0, одштампајте низ.

код

Ц ++ код за генерисање свих могућих сортираних низова

#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

Јава код за генерисање свих могућих сортираних низова

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

Анализа сложености

Сложеност времена

О (н1 ^ 2 + н2 ^ 2) где „Н1“ „Н2“ су дужина АррА и АррБ. Када се елементи наизменично измјењују, то је АррА [0] <АррБ [0] <АррА [1] <АррБ [1] ... У овом случају можемо имати укупно н1 ^ 2 + н2 ^ 2 могућих подскупова. Тако полиномна временска сложеност.

Сложеност простора

О (н1 + н2) где „Н1“ „Н2“ су дужина АррА и АррБ. Излазни низ заузима простор и пошто је величина н1 + н2. Сложеност простора је линеарна.