Берілген екі сұрыпталған массивтің балама элементтерінен барлық мүмкін сұрыпталған массивтерді жасаңыз  


Күрделілік дәрежесі орта
Жиі кіреді Directi Карат PayPal Twilio Яндекс
Array Рекурсия

«Берілген екі сұрыпталған массивтің балама элементтерінен барлық мүмкін сұрыпталған массивтерді құру» мәселесі сізде екі сұрыпталған жиым бар деп тұжырымдайды. Мәселе қоюы мүмкін барлық сұрыпталған массивтерді табуды сұрайды, мысалы, берілген санды екі түрлі массивтің орнына балама етіп орналастыру керек.

мысал  

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. Өлшемнің шығыс жиымын жариялаңыз m + n (екі массивтің де жалпы ұзындығы).
  2. Тексеріңіз boolШарт шындық,
    1. Содан кейін шығатын жиымның ұзындығының 0-ге тең еместігін тексеріп, шығыс жиымын басып шығарыңыз.
      1. Жиым бойынша жүріңіз ArrA және келесіні тексеріңіз
        1. Егер шығым жиымының ұзындығы 0 болса, онда ағымдағы элементті шығару жиымына көшіріңіз, содан кейін функцияны рекурсивті түрде шақырыңыз.
    2. Басқа жағдайда, егер массивтің ағымдағы элементі жиымның алдыңғы элементінен үлкен болса, онда элементті көшіріңіз ArrA шығару массивіне және функцияны рекурсивті түрде шақырады.
  3. Басқа жағдайда, егер boolCondition жалған болса, онда оны айналдырыңыз ArrB және ағымдағы элементінің бар-жоғын тексеріңіз ArrB шығатын жиымның ағымдағы элементінен үлкен
      1. Егер рас болса, онда элементті көшіріңіз ArrB шығару массивіне және функцияны рекурсивті шақырады.
Сондай-ақ, қараңыз
Берілген екі жиынтықтың бөлінгендігін қалай тексеруге болады?

Түсіндіру

«Берілген екі сұрыпталған массивтің балама элементтерінен барлық мүмкін сұрыпталған массивтерді құру» мәселесін келесі жолмен шешуге болады. Мұнда бізге екі сұрыпталған массив берілген ArrA және ArrB. Берілген массивтердің екеуі де сұрыпталған тәртіпте орналасқан. Сонымен, біз барлық мүмкін жағдайларды анықтауымыз керек массивтер ол сұрыпталған түрде салынуы мүмкін. Сондай-ақ, шығарудағы әр балама элемент әр түрлі массивтерден шығуы керек деген тағы бір шарт бар.

Барлық мүмкін жиымдарды білу үшін біз бұл функцияны рекурсивті түрде шақырамыз. Содан кейін біз таңдалатын элементтердің есебін жүргізетін логикалық айнымалыны сақтаймыз. Яғни элемент ағымдағы ArrA немесе ArrB-дан алынған. Егер логикалық айнымалы шын болса, онда біз ArrA бірінші жиымынан элемент таңдаймыз. егер логикалық айнымалы жалған болса, онда біз ArrB екінші жиымынан элементті таңдаймыз. Егер логикалық айнымалы шын болса, онда біз массивтің ұзындығының 0-ге тең еместігін немесе жай 0-ден үлкен екенін тексеретін боламыз, содан кейін әрдайым шығатын жиымды басып шығаратын боламыз.

Егер логикалық шарт шын болса, біз ArrA массивін айналып өтеміз. Содан кейін ағымдағы жиым элементін шығару жиымына көшіріңіз. Сонда біз оған барлық қажетті аргументтерді беретін функцияны рекурсивті деп атаймыз. Егер логикалық шарт жалған болса. Содан кейін ArrB-ді шығаратын массивтен көшіру және жаңарту үшін қолданамыз. Шығару жиымының ұзындығы 0 болған сайын массивті басып шығарыңыз.

Сондай-ақ, қараңыз
Өнімнің максималды ішкі жиыны

код  

Барлық мүмкін сұрыпталған массивтерді құруға арналған C ++ коды

#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

Барлық мүмкін сұрыпталған массивтерді құруға арналған Java коды

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

Күрделілікті талдау  

Уақыттың күрделілігі

O (n1 ^ 2 + n2 ^ 2) қайда “N1” және “N2” ArrA және ArrB ұзындығы. Элементтер ауыспалы болған кезде, яғни ArrA [0] <ArrB [0] <ArrA [1] <ArrB [1] ... Бұл жағдайда бізде барлығы n1 ^ 2 + n2 ^ 2 мүмкін ішкі жиындар болуы мүмкін. Осылайша уақыттың көпмүшелік күрделілігі.

Сондай-ақ, қараңыз
Сирек кестені қолдану арқылы жиынтық сұранысы

Ғарыштың күрделілігі

O (n1 + n2) қайда “N1” және “N2” ArrA және ArrB ұзындығы. Бос орын шығыс жиыммен қабылданады және өлшемі n1 + n2 болғандықтан. Кеңістіктің күрделілігі сызықтық болып табылады.