ສ້າງບັນດາຂອດຈັດລຽງທີ່ເປັນໄປໄດ້ທັງ ໝົດ ຈາກອົງປະກອບສະຫຼັບຂອງສອງແຖວທີ່ຈັດໃຫ້


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Directi ລັດ PayPal Twilio Yandex
Array Recursion

ບັນຫາ“ ສ້າງຂອດຈັດຮຽງທີ່ເປັນໄປໄດ້ທັງ ໝົດ ຈາກອົງປະກອບອື່ນຂອງສອງແຖວທີ່ຈັດລຽງລໍາດັບໃຫ້” ລັດທີ່ສົມມຸດວ່າທ່ານມີສອງປະເພດຈັດລຽງ. ຄຳ ຖະແຫຼງທີ່ມີບັນຫາຂໍໃຫ້ຊອກຫາບັນດາຂບວນທີ່ຈັດລຽງ ລຳ ດັບທີ່ເປັນໄປໄດ້, ຈຳ ນວນດັ່ງກ່າວຄວນໄດ້ຮັບການຈັດແຈງເປັນທາງເລືອກຈາກສອງແຖວທີ່ແຕກຕ່າງກັນ.

ຍົກຕົວຢ່າງ

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 + ນ (ຄວາມຍາວທັງ ໝົດ ຂອງອາຄານທັງສອງ).
  2. ກວດສອບວ່າ boolCondition ແມ່ນຄວາມຈິງ,
    1. ຫຼັງຈາກນັ້ນໃຫ້ກວດເບິ່ງວ່າຄວາມຍາວຂອງຂບວນຜົນຜະລິດບໍ່ເທົ່າກັບ 0, ແລ້ວພິມແຖວແຖວຜົນຜະລິດ.
      1. ຂ້າມອາເລ ArrA ແລະກວດເບິ່ງຕໍ່ໄປນີ້
        1. ຖ້າຄວາມຍາວຂອງຂອດຜົນຜະລິດແມ່ນ 0 ແລ້ວຄັດລອກອົງປະກອບປັດຈຸບັນໃສ່ແຖວຜົນຜະລິດຫຼັງຈາກນັ້ນເອີ້ນຄືນການເຮັດວຽກ.
    2. ອື່ນຖ້າວ່າອົງປະກອບຂບວນປັດຈຸບັນໃຫຍ່ກວ່າຫົວຂໍ້ array ຂອງຜົນຜະລິດທີ່ຜ່ານມາ, ຫຼັງຈາກນັ້ນຄັດລອກ Element ຈາກ ArrA ເຂົ້າໄປໃນແຖວຂອງຜົນຜະລິດແລະເອີ້ນຄືນການເຮັດວຽກ.
  3. ອື່ນຖ້າ boolCondition ບໍ່ຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນກໍ່ຈະຂ້າມ ArrB ແລະກວດເບິ່ງວ່າອົງປະກອບປັດຈຸບັນຂອງ ArrB ແມ່ນໃຫຍ່ກວ່າປັດຈຸບັນຂອງຂບວນການສະແດງຜົນຜະລິດ
      1. ຖ້າຫາກວ່າເປັນຄວາມຈິງຫຼັງຈາກນັ້ນຄັດລອກສ່ວນປະກອບຈາກ ArrB ໄປທີ່ແຖວຜົນຜະລິດແລະເອີ້ນຄືນການເຮັດວຽກ.

ຄໍາອະທິບາຍ

ບັນຫາ“ ສ້າງຂອດຈັດຮຽງທີ່ເປັນໄປໄດ້ທັງ ໝົດ ຈາກອົງປະກອບອື່ນຂອງສອງຂອດຈັດຮຽງໃຫ້” ສາມາດແກ້ໄຂໄດ້ໃນລັກສະນະດັ່ງຕໍ່ໄປນີ້. ຕໍ່ໄປນີ້ພວກເຮົາໄດ້ຮັບສອງຈັດລຽງຕາມແຖວ ArrA ແລະ ArrB. ທັງສອງແຖວຂອງອາຄານທີ່ໃຫ້ໄວ້ແມ່ນຈັດລຽງຕາມ ລຳ ດັບ. ສະນັ້ນ, ພວກເຮົາຕ້ອງຊອກຮູ້ທຸກຄວາມເປັນໄປໄດ້ ອາຄານ ເຊິ່ງສາມາດໄດ້ຮັບການກໍ່ສ້າງໃນລັກສະນະການຈັດລຽງເປັນ. ມັນຍັງມີອີກເງື່ອນໄຂ ໜຶ່ງ ທີ່ແຕ່ລະອົງປະກອບ ສຳ ຮອງໃນຜົນຜະລິດຄວນມາຈາກຂບວນທີ່ແຕກຕ່າງກັນ.

ພວກເຮົາຈະໂທຫາຟັງຊັ່ນນັ້ນຄືນ ໃໝ່ ເພື່ອຊອກຫາຜົນໄດ້ຮັບທີ່ເປັນໄປໄດ້ທັງ ໝົດ. ຫຼັງຈາກນັ້ນພວກເຮົາຮັກສາຕົວແປ boolean ທີ່ຕິດຕາມອົງປະກອບທີ່ຈະຖືກເກັບ. ນັ້ນແມ່ນອົງປະກອບທີ່ມາຈາກ ArrA ຫຼື ArrB ປັດຈຸບັນ. ຖ້າຕົວແປ boolean ແມ່ນຄວາມຈິງ, ຫຼັງຈາກນັ້ນພວກເຮົາເລືອກເອົາອົງປະກອບຈາກ ArrA array ທຳ ອິດ. ຖ້າຫາກວ່າຕົວແປ boolean ບໍ່ຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນພວກເຮົາເລືອກເອົາອົງປະກອບຈາກ ArrB ທີສອງ array. ຖ້າຕົວແປ Boolean ແມ່ນຄວາມຈິງ, ພວກເຮົາຈະກວດເບິ່ງວ່າຄວາມຍາວຂອງ array ບໍ່ເທົ່າກັບ 0 ຫຼືພຽງແຕ່ໃຫຍ່ກວ່າ 0, ຈາກນັ້ນທຸກໆຄັ້ງທີ່ພວກເຮົາ ກຳ ລັງຈະພິມ array ຂອງຜົນຜະລິດ.

ພວກເຮົາ ກຳ ລັງຈະຂ້າມ ArrA ຖ້າເງື່ອນໄຂ boolean ແມ່ນຖືກຕ້ອງ. ຫຼັງຈາກນັ້ນ, ຄັດລອກອົງປະກອບຂບວນປັດຈຸບັນເຂົ້າໃນແຖວຜົນຜະລິດ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາເອີ້ນຄືນການເຮັດວຽກທີ່ຜ່ານການໂຕ້ຖຽງທີ່ ຈຳ ເປັນທັງ ໝົດ ຕໍ່ມັນ. ຖ້າວ່າສະພາບການບູຊາແມ່ນບໍ່ຖືກຕ້ອງ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາໃຊ້ 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. ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາ polynomial.

ຄວາມສັບສົນໃນອະວະກາດ

O (n1 + n2) ບ່ອນທີ່ "n1" ແລະ "n2" ແມ່ນຄວາມຍາວຂອງ ArrA ແລະ ArrB. ພື້ນທີ່ຖືກປະຕິບັດໂດຍຂບວນການຜະລິດແລະນັບຕັ້ງແຕ່ຂະ ໜາດ n1 + n2. ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນເປັນເສັ້ນ.