Максімізацыя элементаў з дапамогай іншага масіва


Узровень складанасці серада
Часта пытаюцца ў амазонка Фанатыкі Фуркайты
масіў гашыш сартаванне

Дапусцім, мы далі два цэлыя масівы аднолькавага памеру 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 * п.
  2. Спачатку захоўваеце другі элементы масіва ў створаным масіве, а потым першыя элементы масіва.
  3. Сартаванне масіва ў парадку не па ўзрастанні.
  4. Захоўваеце n значэнняў масіва ў камплект.
  5. Размясціце іх у парадку, бо яны паступаюць як уваход, спачатку бярэм array2 і правяраем, ці ёсць яго элемент у наборы, і захоўваем іх у трэцім масіве з 0th Індэкс.
  6. Паўтарыце апісаны вышэй працэс для першага масіва.
  7. Раздрукуйце выніковы масіў.

Тлумачэнне

У нас двое цэлыя масіў. Нам трэба максімальна павялічыць першы масіў такім чынам, каб утвораны такім чынам масіў утрымліваў спачатку другі элемент масіва, а потым першы масіў. Ён павінен утрымліваць n унікальныя і найлепшыя элементы абодвух масіваў. Варта падтрымліваць парадак, гэта значыць, калі элемент прыходзіць першым, ён таксама павінен быць першым у другім масіве. Каб вырашыць гэта, стварыце масіў памерам 2 * n, таму што ў нас масіў, памер якога складае n, і нам проста трэба захоўваць элементы абодвух масіваў.

Захоўваеце элементы другога масіва спачатку ў масіве, які мы стварылі, а затым захоўваем элементы першага масіва ў створаным масіве. Мы робім гэта, таму што збіраемся ўставіць усе значэнні створанага масіва, якія трэба ўсталяваць. Таму што для вырашэння гэтага кода мы будзем выкарыстоўваць набор. Пасля ўстаўкі ўсіх значэнняў створанага масіва ў набор. Мы адсартуем масіў у неўзыходзячай паслядоўнасці.

Мы зробім месца ў Set для ўстаўкі значэнняў з масіва да n разоў. N раз - за, у нас ужо адсартаваны масіў у неўзыходзячай паслядоўнасці, нам проста патрэбныя першыя n элементаў, каб зрабіць з ім некаторыя аперацыі. Пасля ўстаўкі Set мы маем найбольшыя n значэнняў у наборы. Цяпер нам трэба арганізаваць гэта значэнне ў адпаведнасці з іх парадкам, калі яны паступаюць на ўваход, таму мы будзем пераходзіць масіў другім, па-першае, таму што гэты масіў з'яўляецца нашым прыярытэтам. Такім чынам, калі мы знайшлі любы з элементаў масіва, другі прысутны ў мностве. Мы абнавім гэты масіў, створаны з 0-й пазіцыі, а таксама праверым першы масіў і абнавім яго значэнні ў трэцім масіве.

Цяпер абнавіце значэнні array3 на array1 і print 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 * часопіс n) дзе "П" - колькасць элементаў у масіве.

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве.

Спасылкі