Максимальний масив із двох заданих масивів, що зберігають порядок однаковий  


Рівень складності Medium
Часто запитують у Accenture Амазонка Делівері Факти Фуркіти Номери OYO Publicis Sapient 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. Проведіть одночасно обидва вектори та вставте на карту більші значення обох векторів разом із частотою елемента.
  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 журнал n) де "N" - довжина масивів.

Дивись також
Максимальна відстань у масиві

Складність простору

О (п) де "N" - довжина масивів.