ಕೊಟ್ಟಿರುವ ಎರಡು ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳ ಪರ್ಯಾಯ ಅಂಶಗಳಿಂದ ಸಾಧ್ಯವಿರುವ ಎಲ್ಲಾ ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳನ್ನು ರಚಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಡೈರೆಕ್ಟಿ ಕಾರಟ್ ಪೇಪಾಲ್ ಟ್ವಿಲಿಯೊ ಯಾಂಡೆಕ್ಸ್
ಅರೇ ಪುನರಾವರ್ತನೆ

"ಎರಡು ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳ ಪರ್ಯಾಯ ಅಂಶಗಳಿಂದ ಸಾಧ್ಯವಿರುವ ಎಲ್ಲಾ ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳನ್ನು ರಚಿಸಿ" ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ಎರಡು ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳನ್ನು ಹೊಂದಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ಸಾಧ್ಯವಿರುವ ಎಲ್ಲಾ ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ, ಅಂತಹ ಸಂಖ್ಯೆಯನ್ನು ಎರಡು ವಿಭಿನ್ನ ಸರಣಿಗಳಿಂದ ಪರ್ಯಾಯವಾಗಿ ಜೋಡಿಸಬೇಕು.

ಉದಾಹರಣೆ

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. ಗಾತ್ರದ output ಟ್‌ಪುಟ್ ಶ್ರೇಣಿಯನ್ನು ಘೋಷಿಸಿ m + n (ಎರಡೂ ಸರಣಿಗಳ ಒಟ್ಟು ಉದ್ದ).
  2. ಪರಿಶೀಲಿಸಿ boolCondition ಇದು ಸತ್ಯ,
    1. ನಂತರ array ಟ್‌ಪುಟ್ ರಚನೆಯ ಉದ್ದವು 0 ಕ್ಕೆ ಸಮನಾಗಿಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಿ, ನಂತರ output ಟ್‌ಪುಟ್ ಅರೇ ಅನ್ನು ಮುದ್ರಿಸಿ.
      1. ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗಿರಿ ಅರ್ರಾ ಮತ್ತು ಕೆಳಗಿನವುಗಳನ್ನು ಪರಿಶೀಲಿಸಿ
        1. Ar ಟ್ಪುಟ್ ಅರೇನ ಉದ್ದ 0 ಆಗಿದ್ದರೆ ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು array ಟ್ಪುಟ್ ಅರೇಗೆ ನಕಲಿಸಿ ನಂತರ ಪುನರಾವರ್ತಿತವಾಗಿ ಕಾರ್ಯವನ್ನು ಕರೆಯಿರಿ.
    2. ಪ್ರಸ್ತುತ ರಚನೆಯ ಅಂಶವು ಹಿಂದಿನ output ಟ್‌ಪುಟ್ ಅರೇ ಅಂಶಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದ್ದರೆ, ನಂತರ ಅಂಶವನ್ನು ನಕಲಿಸಿ ಅರ್ರಾ array ಟ್ಪುಟ್ ಅರೇಗೆ ಮತ್ತು ಪುನರಾವರ್ತಿತವಾಗಿ ಕಾರ್ಯವನ್ನು ಕರೆಯಿರಿ.
  3. ಬೂಲ್ ಕಂಡೀಷನ್ ಸುಳ್ಳಾಗಿದ್ದರೆ, ನಂತರ ಅರ್ರ್ಬಿ ಮತ್ತು ಪ್ರಸ್ತುತ ಅಂಶವಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ ಅರ್ರ್ಬಿ output ಟ್‌ಪುಟ್ ರಚನೆಯ ಪ್ರಸ್ತುತ ಅಂಶಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದೆ
      1. ನಿಜವಾಗಿದ್ದರೆ ಅಂಶವನ್ನು ನಕಲಿಸಿ ಅರ್ರ್ಬಿ array ಟ್ಪುಟ್ ರಚನೆಗೆ ಮತ್ತು ಪುನರಾವರ್ತಿತವಾಗಿ ಕಾರ್ಯವನ್ನು ಕರೆಯಿರಿ.

ವಿವರಣೆ

“ಎರಡು ವಿಂಗಡಿಸಲಾದ ಸರಣಿಗಳ ಪರ್ಯಾಯ ಅಂಶಗಳಿಂದ ಸಾಧ್ಯವಿರುವ ಎಲ್ಲಾ ವಿಂಗಡಿಸಲಾದ ಸರಣಿಗಳನ್ನು ರಚಿಸಿ” ಎಂಬ ಸಮಸ್ಯೆಯನ್ನು ಈ ಕೆಳಗಿನ ರೀತಿಯಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಇಲ್ಲಿ ನಮಗೆ ಎರಡು ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳನ್ನು ನೀಡಲಾಗಿದೆ ಅರ್ರಾ ಮತ್ತು ಅರ್ರ್ಬಿ. ನೀಡಿರುವ ಎರಡೂ ಸರಣಿಗಳು ವಿಂಗಡಿಸಲಾದ ಕ್ರಮದಲ್ಲಿವೆ. ಆದ್ದರಿಂದ, ನಾವು ಸಾಧ್ಯವಿರುವ ಎಲ್ಲವನ್ನೂ ಕಂಡುಹಿಡಿಯಬೇಕು ಸರಣಿಗಳು ಇದನ್ನು ವಿಂಗಡಿಸಲಾದ ರೀತಿಯಲ್ಲಿ ನಿರ್ಮಿಸಬಹುದು. Output ಟ್ಪುಟ್ನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಪರ್ಯಾಯ ಅಂಶವು ವಿಭಿನ್ನ ಸರಣಿಗಳಿಂದ ಬರಬೇಕು ಎಂಬ ಇನ್ನೊಂದು ಷರತ್ತು ಸಹ ಇದೆ.

ಸಂಭವನೀಯ output ಟ್‌ಪುಟ್ ಅರೇಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಆ ಕಾರ್ಯವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಕರೆಯುತ್ತೇವೆ. ನಂತರ ನಾವು ಬೂಲಿಯನ್ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಇರಿಸಿಕೊಳ್ಳುತ್ತೇವೆ ಅದು ಆರಿಸಬೇಕಾದ ಅಂಶಗಳ ಜಾಡನ್ನು ಇಡುತ್ತದೆ. ಅದು ಅಂಶವು ಪ್ರಸ್ತುತ ಆರ್ಆರ್ಎ ಅಥವಾ ಆರ್ಆರ್ಬಿಯಿಂದ ಬಂದಿದೆ. ಬೂಲಿಯನ್ ವೇರಿಯೇಬಲ್ ನಿಜವಾಗಿದ್ದರೆ, ನಾವು ಮೊದಲ ಶ್ರೇಣಿಯ ಅರ್ರಾದಿಂದ ಒಂದು ಅಂಶವನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತೇವೆ. ಬೂಲಿಯನ್ ವೇರಿಯಬಲ್ ತಪ್ಪಾಗಿದ್ದರೆ, ನಾವು ಎರಡನೇ ಶ್ರೇಣಿಯ ಆರ್ಆರ್ಬಿಯಿಂದ ಅಂಶವನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತೇವೆ. ಬೂಲಿಯನ್ ವೇರಿಯೇಬಲ್ ನಿಜವಾಗಿದ್ದರೆ, ರಚನೆಯ ಉದ್ದವು 0 ಕ್ಕೆ ಸಮನಾಗಿಲ್ಲವೇ ಅಥವಾ 0 ಕ್ಕಿಂತ ಸರಳವಾಗಿಲ್ಲವೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಲಿದ್ದೇವೆ, ನಂತರ ಪ್ರತಿ ಬಾರಿ ನಾವು output ಟ್‌ಪುಟ್ ಅರೇ ಅನ್ನು ಮುದ್ರಿಸಲು ಹೋಗುತ್ತೇವೆ.

ಬೂಲಿಯನ್ ಸ್ಥಿತಿ ನಿಜವಾಗಿದ್ದರೆ ನಾವು ಅರೇ ಎಂಬ ಶ್ರೇಣಿಯನ್ನು ದಾಟಲಿದ್ದೇವೆ. ನಂತರ ಪ್ರಸ್ತುತ ರಚನೆಯ ಅಂಶವನ್ನು output ಟ್‌ಪುಟ್ ರಚನೆಗೆ ನಕಲಿಸಿ. ನಂತರ ನಾವು ಅಗತ್ಯವಿರುವ ಎಲ್ಲ ವಾದಗಳನ್ನು ಹಾದುಹೋಗುವ ಕಾರ್ಯವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಕರೆಯುತ್ತೇವೆ. ಬೂಲಿಯನ್ ಸ್ಥಿತಿ ಸುಳ್ಳಾಗಿದ್ದರೆ. ನಂತರ ನಾವು ನಮ್ಮ output ಟ್‌ಪುಟ್ ಶ್ರೇಣಿಯನ್ನು ನಕಲಿಸಲು ಮತ್ತು ನವೀಕರಿಸಲು ArrB ಅನ್ನು ಬಳಸುತ್ತೇವೆ. ಮತ್ತು ಪ್ರತಿ ಬಾರಿ output ಟ್‌ಪುಟ್ ರಚನೆಯ ಉದ್ದ 0 ಆಗಿದ್ದಾಗ, ನಂತರ ಶ್ರೇಣಿಯನ್ನು ಮುದ್ರಿಸಿ.

ಕೋಡ್

ಎಲ್ಲಾ ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳನ್ನು ರಚಿಸಲು ಸಿ ++ ಕೋಡ್

#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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

O (n1 ^ 2 + n2 ^ 2) ಅಲ್ಲಿ “N1” ಮತ್ತು “N2” ArrA ಮತ್ತು ArrB ನ ಉದ್ದ. ಅಂಶಗಳು ಪರ್ಯಾಯವಾಗಿದ್ದಾಗ, ಅದು ಅರ್ರಾ [0] <ಅರ್ರ್ಬಿ [0] <ಅರ್ರಾ [1] <ಅರ್ರ್ಬಿ [1]… ಈ ಸಂದರ್ಭದಲ್ಲಿ, ನಾವು ಒಟ್ಟು n1 ^ 2 + n2 ^ 2 ಸಂಭವನೀಯ ಉಪವಿಭಾಗಗಳನ್ನು ಹೊಂದಬಹುದು. ಆದ್ದರಿಂದ ಬಹುಪದ ಸಮಯದ ಸಂಕೀರ್ಣತೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ 1 + ಎನ್ 2) ಅಲ್ಲಿ “N1” ಮತ್ತು “N2” ArrA ಮತ್ತು ArrB ನ ಉದ್ದ. Space ಟ್ಪುಟ್ ಅರೇನಿಂದ ಸ್ಥಳವನ್ನು ತೆಗೆದುಕೊಳ್ಳಲಾಗುತ್ತದೆ ಮತ್ತು ಗಾತ್ರವು n1 + n2 ಆಗಿರುತ್ತದೆ. ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ.