다른 배열을 사용하여 요소 최대화

난이도 중급
자주 묻는 질문 아마존 광신자 포카이트
배열 해시 정렬조회수 20

n 크기가 같은 두 개의 정수 배열을 제공했다고 가정합니다. 두 배열 모두 양수를 포함합니다. 문제 설명은 두 번째 배열을 우선 순위로 유지하는 두 번째 배열 요소를 사용하여 첫 번째 배열을 최대화하도록 요청합니다 (두 번째 배열의 요소는 출력에서 ​​먼저 표시되어야 함). 이렇게 형성된 배열에는 n 두 배열의 독특하지만 가장 큰 요소.

arr1[] = {3,7,9,1,4}
arr2[] = {2,8,6,5,3}
{8, 6, 5, 7, 9}
arr1[] = {9,3,2}
arr2[] = {6,4,1}
{6, 4, 9}

암호알고리즘

  1. 를 생성 정렬 크기 2 * n.
  2. 먼저 두 번째 배열 요소를 생성 된 배열에 저장 한 다음 첫 번째 배열 요소를 저장합니다.
  3. 오름차순이 아닌 순서로 배열을 정렬합니다.
  4. 배열의 n 값을 세트.
  5. 먼저 array2를 가져 와서 해당 요소가 세트에 있는지 확인하고 0에서 세 번째 배열에 저장하여 입력으로 오는 순서대로 정렬합니다.th 색인.
  6. 첫 번째 어레이에 대해 위 과정을 반복합니다.
  7. 결과 배열을 인쇄합니다.

설명

우리는 두 가지 정수 정렬. 이렇게 형성된 배열이 두 번째 배열 요소를 먼저 포함한 다음 첫 번째 배열을 포함하는 방식으로 첫 번째 배열을 최대화해야합니다. 포함해야합니다 n 두 배열의 독특하고 가장 큰 요소. 순서는 유지되어야합니다. 즉, 요소가 먼저 오면 두 번째 배열에서도 먼저 와야합니다. 이 문제를 해결하려면 크기가 n 인 배열이 있고 두 배열의 요소 만 저장하면되므로 크기 2 * n의 배열을 만듭니다.

두 번째 배열의 요소를 먼저 만든 배열에 저장 한 다음 첫 번째 배열의 요소를 생성 된 배열에 저장합니다. 설정하기 위해 생성 된 배열의 모든 값을 삽입하기 때문에이 작업을 수행합니다. 이 코드를 풀기 위해 우리는 세트를 사용할 것입니다. 생성 된 배열의 모든 값을 세트에 삽입 한 후. 오름차순이 아닌 순서로 배열을 정렬합니다.

Set에 배열의 값을 최대 n 번 삽입 할 수있는 위치를 만듭니다. N 번은 이미 비 오름차순으로 정렬 된 배열을 가지고 있습니다. 이제 몇 가지 작업을 수행하려면 처음 n 개 요소 만 필요합니다. Set을 삽입 한 후에는 집합에서 가장 큰 n 개의 값을 갖게됩니다. 이제 우리는 입력 된 순서에 따라 그 값을 배열해야합니다. 그래서 우리는 그 배열이 우리의 우선 순위이기 때문에 두 번째로 배열을 순회 할 것입니다. 그래서 우리가 Set에 존재하는 두 번째 배열의 요소를 발견하면. 0 번째 위치에서 생성 된 배열을 업데이트하고 첫 번째 배열도 확인하고 배열 XNUMX 번째의 값을 업데이트합니다.

이제 array3의 값을 array1로 업데이트하고 array1을 인쇄합니다. 이것이 우리가 첫 번째 배열을 최대화하고 두 번째 배열을 우선 순위로 삼는 방법입니다.

실시

다른 배열을 사용하여 요소 최대화를위한 C ++ 프로그램

#include <iostream>
#include<algorithm>
#include<unordered_set>

using namespace std;

bool compare(int a, int b)
{
    return a > b;
}
void getMaximizeArray(int arr1[], int arr2[], int n)
{
    int arr3[2*n], j = 0;
    for (int i = 0; i < n; i++)
        arr3[j++] = arr1[i];
    for (int i = 0; i < n; i++)
        arr3[j++] = arr2[i];

    unordered_set<int> SET;

    sort(arr3, arr3 + 2 * n, compare);

    int i = 0;
    while (SET.size() != n)
    {
        if (SET.find(arr3[i]) == SET.end())
            SET.insert(arr3[i]);

        i++;
    }
    j = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr2[i]) != SET.end())
        {
            arr3[j++] = arr2[i];
            SET.erase(arr2[i]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr1[i]) != SET.end())
        {
            arr3[j++] = arr1[i];
            SET.erase(arr1[i]);
        }
    }
    for (int i = 0; i < n; i++)
        arr1[i] = arr3[i];
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    getMaximizeArray(arr1, arr2, n);
    printArray(arr1, n);
}
8 6 5 7 9

다른 어레이를 사용하여 요소 최대화를위한 Java 프로그램

import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.lang.*;

class arrayMaximize
{
    public static void getMaximizeArray(int arr1[], int arr2[], int n)
    {
        int arr3[]=new int[2*n];
        int j = 0;
        for (int i = 0; i < n; i++)
            arr3[j++] = arr1[i];
        for (int i = 0; i < n; i++)
            arr3[j++] = arr2[i];


        Arrays.sort(arr3);

        HashSet<Integer> SET=new HashSet<>();

        int i = (2*n)-1;
        while (SET.size() != n)
        {
            if (!SET.contains(arr3[i]))
                SET.add(arr3[i]);

            i--;
        }


        j = 0;
        for (int a = 0; a < n; a++)
        {
            if (SET.contains(arr2[a]))
            {
                arr3[j++] = arr2[a];
                SET.remove(arr2[a]);
            }
        }

        for (int b = 0; b < n; b++)
        {
            if (SET.contains(arr1[b]))
            {
                arr3[j++] = arr1[b];
                SET.remove(arr1[b]);
            }
        }
        for (int c = 0; c < n; c++)
            arr1[c] = arr3[c];
    }
    public static void printArray(int arr[], int n)
    {
        for (int k = 0; k < n; k++)
            System.out.print(arr[k]+" ");
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        getMaximizeArray(arr1, arr2, n);
        printArray(arr1, n);
    }
}
8 6 5 7 9

다른 어레이를 사용하여 요소를 최대화하기위한 복잡성 분석

시간 복잡성

O (n * log n) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

참조

Translate »