Максімальны масіў з двух дадзеных масіваў, якія падтрымліваюць аднолькавы парадак


Узровень складанасці серада
Часта пытаюцца ў Accenture амазонка Дэліверы Факты Фуркайты Нумары OYO Publicis Sapient Zoho
масіў гашыш

Дапусцім, у нас ёсць два цэлыя лікі масіў аднолькавага памеру н. Абодва масівы могуць утрымліваць і агульныя лічбы. Пастаноўка праблемы просіць сфармаваць выніковы масіў, які змяшчае максімальныя значэнні '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. Правядзіце абодва вектары адначасова і ўпішыце ў карту большыя значэнні абодвух вектараў разам з частатой элемента.
  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) дзе "П" - даўжыня масіваў.

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

Аб (п) дзе "П" - даўжыня масіваў.