從兩個給定排序數組的備用元素生成所有可能的排序數組  


難度級別 中烘焙
經常問 指令 卡拉特 貝寶 Twilio Yandex的
排列 遞歸

問題“從兩個給定的排序數組的備用元素生成所有可能的排序數組”狀態假設您有兩個排序數組。 問題陳述要求找出所有可能的排序數組,以便應從兩個給定的不同數組中交替排列數字。

例  

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. 聲明一個大小為size的輸出數組 m + n (兩個數組的總長度)。
  2. 檢查是否 bool條件 是真的,
    1. 然後檢查輸出數組的長度是否不等於0,然後打印輸出數組。
      1. 遍歷數組 ArrA 並檢查以下內容
        1. 如果輸出數組的長度為0,則將當前元素複製到輸出數組,然後遞歸調用該函數。
    2. 否則,如果當前數組元素大於先前的輸出數組元素,則從 ArrA 放入輸出數組並遞歸調用該函數。
  3. 否則,如果boolCondition為false,則遍歷 ArrB 並檢查當前元素是否 ArrB 大於輸出數組的當前元素
      1. 如果為true,則從中復制元素 ArrB 到輸出數組並遞歸調用該函數。
也可以看看
如何檢查兩個給定的集合是否不相交?

解釋

可以通過以下方式解決“從兩個給定排序數組的備用元素生成所有可能的排序數組”的問題。 在這裡,我們得到了兩個排序的數組 ArrAArrB。 給定的兩個數組均按排序順序。 因此,我們需要找出所有可能的 數組 可以按分類的方式構造。 還有另一個條件,即輸出中的每個備用元素都應來自不同的數組。

我們將遞歸調用該函數以找出所有可能的輸出數組。 然後,我們保留一個布爾變量,該變量跟踪要拾取的元素。 即該元素來自當前的ArrA或ArrB。 如果布爾變量為true,則我們從第一個數組ArrA中選擇一個元素。 否則,如果布爾變量為false,則從第二個數組ArrB中選擇元素。 如果布爾變量為true,我們將檢查數組的長度是否不等於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。 空間複雜度是線性的。