Verilən iki sıralanmış massivin alternativ elementlərindən bütün mümkün sıralanmış massivləri yaradın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Directi Karat PayPal Twilio Yandex
Geyim RecursionBaxılıb 24

Problem, "verilmiş iki sıralanmış massivin alternativ elementlərindən mümkün olan bütün sıralanmış massivləri yaratmaq", iki sıralanmış massiviniz olduğunu düşündüyünüzü bildirir. Problem ifadəsi, mümkün olan bütün sıralanmış massivləri tapmağı xahiş edir, belə ki, bu rəqəm verilmiş iki fərqli massivdən alternativ olaraq düzəldilməlidir.

misal

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

Izahat

Bütün alternativ nömrələr fərqli massivlərdəndir və sıralanır.

Verilən iki sıralanmış massivin alternativ elementlərindən bütün mümkün sıralanmış massivləri yaradınPin

 

Alqoritm

  1. Çıxış ölçüsü ölçüsünü elan edin m + n (hər iki massivin ümumi uzunluğu).
  2. Yoxsa yoxlayın bool Şərt doğrudur,
    1. Sonra çıxış massivinin uzunluğunun 0-a bərabər olmadığını yoxlayın, sonra çıxış massivini çap edin.
      1. Dizini keçin ArA və aşağıdakıları yoxlayın
        1. Çıxış massivinin uzunluğu 0 olarsa, cari elementi çıxış massivinə kopyalayın, sonra rekursiv olaraq funksiyanı çağırın.
    2. Başqa bir halda, cari massiv elementi əvvəlki çıxış massivi elementindən böyükdürsə, onda elementi kopyalayın ArA çıxış massivinə daxil edin və rekursiv olaraq funksiyanı çağırın.
  3. Başqa bir hal, əgər boolCondition yalan olarsa, o zaman keçin ArrB və cari elementinin olub olmadığını yoxlayın ArrB çıxış massivinin cari elementindən böyükdür
      1. Düzdürsə, elementi kopyalayın ArrB çıxış massivinə və rekursiv olaraq funksiyanı çağırın.

Izahat

“Verilən iki sıralanmış massivin alternativ elementlərindən mümkün olan bütün sıralanmış massivləri yaratmaq” problemi aşağıdakı qaydada həll edilə bilər. Burada bizə iki sıralanmış massiv verilir ArAArrB. Verilən massivlərin hər ikisi sıralanmış qaydada. Beləliklə, mümkün olan hər şeyi öyrənməliyik seriallar sıralanmış bir şəkildə inşa edilə bilən. Çıxışdakı hər bir alternativ elementin fərqli massivlərdən gəlməsi lazım olan başqa bir şərt də var.

Mümkün olan bütün çıxış massivlərini tapmaq üçün həmin funksiyanı təkrarən çağıracağıq. Sonra seçiləcək elementləri izləyən bir boole dəyişənini saxlayırıq. Ya element cari ArrA ya da ArrB-dəndir. Mantiqən dəyişən doğrudursa, ilk ArrA massivindən bir element seçirik. boolean dəyişən yanlışdırsa, ikinci ArrB massivindən element seçirik. Mantiqən dəyişən doğrudursa, serialın uzunluğunun 0-a bərabər olmadığını və ya sadəcə 0-dan çox olduğunu yoxlayacağıq, onda hər dəfə çıxış massivini çap edəcəyik.

Mantiq şərti doğrudursa, ArrA massivini keçəcəyik. Sonra cari array elementini çıxış massivinə kopyalayın. Sonra bütün lazımi arqumentləri ötürən funksiyanı rekursiv olaraq çağırırıq. Mantiq vəziyyəti səhvdirsə. Sonra çıxdığımız serialı kopyalamaq və yeniləmək üçün ArrB istifadə edirik. Və hər dəfə çıxış massivinin uzunluğu 0 olduqda, sonra serialı çap edin.

Kodu

Bütün mümkün sıralanmış massivləri yaratmaq üçün C ++ kodu

#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

Mümkün olan bütün sıralanmış massivləri yaratmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n1 ^ 2 + n2 ^ 2) hara “N1” “N2” ArrA və ArrB uzunluğudur. Elementlər dəyişkən olduqda, yəni ArrA [0] <ArrB [0] <ArrA [1] <ArrB [1] ... Bu vəziyyətdə cəmi n1 ^ 2 + n2 ^ 2 alt hissəyə sahib ola bilərik. Beləliklə, bir polinom zaman mürəkkəbliyi.

Kosmik Mürəkkəblik

O (n1 + n2) hara “N1” “N2” ArrA və ArrB uzunluğudur. Boşluq çıxış massivi tərəfindən alınır və ölçüsü n1 + n2 olduğundan. Məkan mürəkkəbliyi xətti xarakter daşıyır.

Translate »