قم بإنشاء كل المصفوفات التي تم فرزها الممكنة من عناصر بديلة لمصفوفتين تم فرزهما


مستوى الصعوبة متوسط
كثيرا ما يطلب في Directi قيراط 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

تفسير

جميع الأرقام البديلة من مصفوفات مختلفة ومرتبة.

قم بإنشاء كل المصفوفات التي تم فرزها الممكنة من عناصر بديلة لمصفوفتين تم فرزهما

 

خوارزمية

  1. قم بتعريف صفيف إخراج بالحجم م + ن (الطول الإجمالي لكل من المصفوفتين).
  2. تحقق فيما لو منطقية صحيح،
    1. ثم تحقق مما إذا كان طول صفيف الإخراج لا يساوي 0 ، ثم اطبع مصفوفة الإخراج.
      1. اجتياز المصفوفة آرا وتحقق مما يلي
        1. إذا كان طول صفيف الإخراج هو 0 ، فقم بنسخ العنصر الحالي إلى مصفوفة الإخراج ثم استدعاء الوظيفة بشكل متكرر.
    2. وإلا إذا كان عنصر الصفيف الحالي أكبر من عنصر مصفوفة الإخراج السابق ، فقم بنسخ العنصر من آرا في صفيف الإخراج واستدعاء الوظيفة بشكل متكرر.
  3. وإلا إذا كانت boolCondition خاطئة ، فاجتاز ملف ارب وتحقق مما إذا كان العنصر الحالي لـ ارب أكبر من العنصر الحالي في صفيف الإخراج
      1. إذا كان صحيحًا ، فانسخ العنصر من ارب إلى مصفوفة الإخراج واستدعاء الوظيفة بشكل متكرر.

تفسير

يمكن حل مشكلة "إنشاء كل المصفوفات المصنفة الممكنة من عناصر بديلة لمصفوفتين مفروزتين" بالطريقة التالية. هنا لدينا مجموعتان من المصفوفات آرا و ارب. كلا المصفوفتين المعطاة مرتبتان بالترتيب. لذا ، نحن بحاجة إلى معرفة كل ما هو ممكن المصفوفات والتي يمكن بناؤها بطريقة مرتبة. هناك أيضًا شرط آخر وهو أن كل عنصر بديل في الإخراج يجب أن يأتي من مصفوفات مختلفة.

سنقوم باستدعاء هذه الوظيفة بشكل متكرر لمعرفة كل مصفوفات الإخراج الممكنة. ثم نحتفظ بمتغير منطقي يتتبع العناصر المراد انتقاؤها. هذا هو العنصر إما من 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

كود جافا لإنشاء كل المصفوفات المصنفة الممكنة

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

تحليل التعقيد

تعقيد الوقت

يا (ن 1 ^ 2 + ن 2 ^ 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. تعقيد الفضاء خطي.