Максимален масив от два дадени масива, поддържащи еднакъв ред


Ниво на трудност M
Често задавани в Accenture Амазонка Делхейвъри FactSet Fourkites OYO Стаи Publicis Sapient Zoho
Array Хашиш

Да предположим, че имаме две цели числа масив със същия размер 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) където "н" е дължината на масивите.

Сложност на пространството

О (п) където "н" е дължината на масивите.