순서를 동일하게 유지하는 두 개의 지정된 어레이의 최대 어레이


난이도 중급
자주 묻는 질문 Accenture 아마존 배달 팩트 셋 포카이트 오요 룸 퍼블리 시스 사피엔 트 조호 (Zoho)
배열 해시

두 개의 정수가 있다고 가정합니다. 정렬 같은 크기 n. 두 배열 모두 공통 숫자도 포함 할 수 있습니다. 문제 설명은 두 배열 모두에서 'n'최대 값을 포함하는 결과 배열을 형성하도록 요청합니다. 첫 번째 배열의 우선 순위가 지정되어야합니다 (첫 번째 배열의 요소가 출력에서 ​​먼저 나타나야 함). 출력 배열은 주어진 두 배열의 최대 요소이지만 공통 요소는 한 번 나오고 먼저 배열의 우선 순위를 지정해야합니다.

입력:

int arr1 [] = {3,7,9,1,4}

int arr2 [] = {2,8,6,5,3}

출력:

{7, 9, 8, 6, 5}

설명 :

7, 9는 첫 번째 배열의 요소이므로 출력에서 ​​첫 번째가됩니다.

입력:

int arr1 [] = {9,3,2}

int arr2 [] = {6,4,1}

출력:

{9, 6, 4}

순서를 동일하게 유지하는 두 개의 주어진 배열에서 최대 배열에 대한 알고리즘

  1. 두 배열을 모두 벡터.
  2. 비 오름차순 시퀀스로 두 벡터를 모두 정렬합니다.
  3. 두 벡터를 동시에 탐색하고 두 벡터의 더 큰 값을 요소의 빈도와 함께 맵에 'n'개 밀어 넣습니다.
  4. 새 벡터 "출력"을 만듭니다.
  5. 공통 요소가 있는지 확인하십시오. 지도 또한 먼저 배열에서 해당 요소를 출력 벡터에 추가합니다.
  6. 맵과 두 번째 배열에도 공통 요소가 있는지 확인한 다음 빈도가 1 인 요소를 선택하고 출력 벡터에 추가합니다.
  7. 결과 벡터 "출력"을 인쇄합니다.

설명

두 배열을 모두 벡터로 변환하고 내림차순으로 정렬합니다. 이를 통해 두 배열의 값을 벡터로 가져올 수 있으며 두 벡터의 시퀀스에서 먼저 더 큰 숫자를 갖게됩니다. 그래서 우리는 'n'을 선택할 수 있습니다. 최대 수 두 배열에서.

공통 요소의 경우를 처리하려면 벡터를 동시에 비교하고 두 배열에서 최대 값을 선택하여 주파수와 함께 맵에 넣습니다.이를 통해 가능한지 확인할 수 있습니다. 공통 요소가 될 경우 n 개의 최대 요소를 맵에 넣을 것입니다. 한 요소를 두 번 이상 발견하면 빈도를 높이고 맵에서 추가 요소로 계산되지 않습니다. 주파수 2, 3 또는 그 이상으로 표시됩니다. 따라서 나중에 순회 할 때이를 무시하고 첫 번째 어레이의 우선 순위를 지정할 수 있습니다.

우리는 배열과지도를 모두 횡단 할 것입니다. 첫째, 맵과 함께 첫 번째 배열을 탐색해야합니다. 맵과 배열에서 공통 요소가 발견되면 결과로 생성 한 출력 벡터로 밀어 넣어야합니다. 그런 다음 공통 요소도 결과에 저장 될 수 있으므로 두 번째 배열을 순회 할 것이므로 여기에서는 두 번째 배열 및 맵의 공통 값과 함께 해당 요소의 빈도가지도에서 1인지 확인합니다. , 그러면 우리는 그것을 결과 벡터로 밀어 넣을 것입니다. 마지막으로 벡터를 인쇄합니다.

실시

순서를 동일하게 유지하는 두 개의 주어진 배열에서 최대 배열을위한 C ++ 프로그램

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

void makeGreaterFirstArray(int A[], int B[], int n)
{
    vector<int> V1(A, A+n);
    vector<int> V2(B, B+n);
    sort(V1.begin(), V1.end(), greater<int>());
    sort(V2.begin(), V2.end(), greater<int>());

    unordered_map<int, int> MAP;
    int i = 0, j = 0;
    while (MAP.size() < n)
    {
        if (V1[i] >= V2[j])
        {
            MAP[V1[i]]++;
            i++;
        }
        else
        {
            MAP[V2[j]]++;
            j++;
        }
    }
    vector<int> output;
    for (int i = 0; i < n; i++)
        if (MAP.find(A[i]) != MAP.end())
            output.push_back(A[i]);

    for (int i = 0; i < n; i++)
        if (MAP.find(B[i]) != MAP.end() && MAP[B[i]] == 1)
            output.push_back(B[i]);

    for (int i = 0; i < n; i++)
        cout << output[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    makeGreaterFirstArray(arr1, arr2, n);
    return 0;
}
7 9 8 6 5

순서를 동일하게 유지하는 두 개의 주어진 배열에서 최대 배열을위한 Java 프로그램

import java.util.Collections;
import java.util.Vector;
import java.util.HashMap;
import java.util.Arrays;
import java.util.stream.Collectors;

class findsubarray
{
    public static void makeGreaterFirstArray(int []A, int []B, int n)
    {
        Vector<Integer> V1 = new Vector<>();
        Vector<Integer> V2 = new Vector<>();

        Integer[] I1 = Arrays.stream( A ).boxed().toArray( Integer[]::new );
        Integer[] I2 = Arrays.stream( B ).boxed().toArray( Integer[]::new );


        Collections.addAll(V1, I1);
        Collections.addAll(V2, I2);

        Collections.sort(V1, Collections.reverseOrder());
        Collections.sort(V2, Collections.reverseOrder());


        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int i = 0, j = 0;
        while (MAP.size() < n)
        {
            if (V1.get(i) >= V2.get(j))
            {
                if(MAP.containsKey(V1.get(i)))
                {
                    MAP.put(V1.get(i), MAP.get(V1.get(i))+1);
                    i++;
                }
                else
                {
                    MAP.put(V1.get(i),1);
                    i++;
                }
            }
            else
            {
                if(MAP.containsKey(V2.get(j)))
                {
                    MAP.put(V2.get(j), MAP.get(V2.get(j))+1);
                    j++;
                }
                else
                {
                    MAP.put(V2.get(j),1);
                    j++;
                }
            }
        }
        Vector<Integer> output = new Vector<Integer>();

        for (int a = 0; a < n; a++)
            if (MAP.containsKey(A[a]))
                output.add(A[a]);

        for (int b = 0; b < n; b++)
            if (MAP.containsKey(B[b]) && MAP.get(B[b])==1)
                output.add(B[b]);


        System.out.println(output);
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        makeGreaterFirstArray(arr1, arr2, n);
    }
}
[7, 9, 8, 6, 5]

순서를 동일하게 유지하는 두 개의 주어진 어레이에서 최대 어레이에 대한 복잡성 분석

시간 복잡성

O (n log n) 어디에 "엔" 배열의 길이입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 길이입니다.