지정된 두 개의 정렬 된 배열의 대체 요소에서 가능한 모든 정렬 된 배열 생성

난이도 중급
자주 묻는 질문 지시 캐럿 페이팔 Twilio Yandex 주차
배열 재귀조회수 24

"지정된 정렬 된 두 배열의 대체 요소에서 가능한 모든 정렬 된 배열 생성"문제는 두 개의 정렬 된 배열이 있다고 가정합니다. 문제 설명은 가능한 모든 정렬 된 배열을 찾아 내도록 요청합니다. 따라서 숫자는 주어진 두 개의 다른 배열에서 교대로 배열되어야합니다.

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. 확인 bool조건 사실이다,
    1. 그런 다음 출력 배열의 길이가 0이 아닌지 확인한 다음 출력 배열을 인쇄합니다.
      1. 배열 탐색 아라 다음을 확인하십시오
        1. 출력 배열의 길이가 0이면 현재 요소를 출력 배열에 복사 한 다음 함수를 재귀 적으로 호출합니다.
    2. 그렇지 않으면 현재 배열 요소가 이전 출력 배열 요소보다 크면 다음에서 요소를 복사합니다. 아라 출력 배열에 넣고 함수를 재귀 적으로 호출합니다.
  3. 그렇지 않으면 boolCondition이 false이면 아르비 현재 요소가 아르비 출력 배열의 현재 요소보다 큽니다.
      1. 참이면 다음에서 요소를 복사하십시오. 아르비 출력 배열에 추가하고 함수를 재귀 적으로 호출합니다.

설명

"지정된 정렬 된 두 배열의 대체 요소에서 가능한 모든 정렬 된 배열 생성"문제는 다음과 같은 방식으로 해결할 수 있습니다. 여기에 두 개의 정렬 된 배열이 있습니다. 아라아르비. 주어진 두 배열은 모두 정렬 된 순서입니다. 따라서 가능한 모든 것을 찾아야합니다. 배열 정렬 된 방식으로 구성 할 수 있습니다. 출력의 각 대체 요소가 서로 다른 배열에서 나와야한다는 또 다른 조건이 있습니다.

가능한 모든 출력 배열을 찾기 위해 해당 함수를 재귀 적으로 호출합니다. 그런 다음 선택할 요소를 추적하는 부울 변수를 유지합니다. 이는 요소가 현재 ArrA 또는 ArrB의 요소입니다. 부울 변수가 참이면 첫 번째 배열 ArrA에서 요소를 선택합니다. 그렇지 않으면 부울 변수가 거짓이면 두 번째 배열 ArrB에서 요소를 선택합니다. Boolean 변수가 참이면 배열의 길이가 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이므로 출력 배열이 공간을 차지합니다. 공간 복잡성은 선형입니다.

Translate »