צור את כל המערכים הממוינים האפשריים מאלמנטים חלופיים של שני מערכים ממוינים נתונים  


רמת קושי בינוני
נשאל לעתים קרובות דירקטי קראט פייפאל 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. הכריז על מערך פלט בגודל m + n (אורך כולל של שני המערכים).
  2. תבדוק אם boolCondition נכון,
    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. מורכבות החלל היא לינארית.