Створити всі можливі відсортовані масиви з альтернативних елементів двох заданих відсортованих масивів  


Рівень складності Medium
Часто запитують у Directi Karat PayPal Twilio Яндекс
масив Рекурсія

У задачі «Створення всіх можливих відсортованих масивів із альтернативних елементів двох заданих відсортованих масивів» зазначено, що припускаємо, що у вас є два відсортовані масиви. Постановка задачі вимагає з'ясувати всі можливі відсортовані масиви, так що число повинно розташовуватися по черзі з двох даних різних масивів.

Приклад  

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

Пояснення

Усі альтернативні номери отримані з різних масивів та відсортовані.

Створити всі можливі відсортовані масиви з альтернативних елементів двох заданих відсортованих масивівPin

 

Алгоритм  

  1. Оголосіть вихідний масив розміру m + n (загальна довжина обох масивів).
  2. Перевірте, чи є boolCondition правда,
    1. Потім перевірте, чи довжина вихідного масиву не дорівнює 0, а потім надрукуйте вихідний масив.
      1. Перемістити масив ArrA і перевірте наступне
        1. Якщо довжина вихідного масиву дорівнює 0, скопіюйте поточний елемент у вихідний масив, а потім рекурсивно викличте функцію.
    2. В іншому випадку, якщо поточний елемент масиву більше попереднього елемента вихідного масиву, скопіюйте елемент із ArrA у вихідний масив і рекурсивно викликати функцію.
  3. В іншому випадку, якщо boolCondition хибне, перейдіть до ArrB і перевірте, чи поточний елемент ArrB більше поточного елемента вихідного масиву
      1. Якщо true, скопіюйте елемент із 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. Складність простору лінійна.