Об’єднати сортовані масиви з розчином штрих-коду


Рівень складності Легко
Часто запитують у саман Амазонка Apple Bloomberg ByteDance Cisco eBay Expedia Facebook Goldman Sachs Google IBM LinkedIn ліфт Microsoft Netflix оракул Жива картина Убер VMware Yahoo Яндекс
масив Два покажчика

У задачі “Об’єднати відсортовані масиви” нам подано два масиви сортується в порядку спадання. Перший масив заповнений не повністю і має достатньо місця для розміщення всіх елементів другого масиву. Ми повинні об’єднати два масиви таким чином, щоб перший масив містив елементи обох масивів і сортувався в не спадаючі порядку.

Приклад

{1 , 2 , 3 , - , - , -}
{2 , 6 , 7}
1 2 2 3 6 7
{1 , 1 , 1 ,  - , -}
{2 , 4}
1 1 1 2 4

Підхід (сортування)

Ми можемо перенести всі елементи другого масиву в перший. Потім ми можемо відсортувати перший масив, щоб отримати необхідний результат.

Алгоритм

  1. Для i = 0 до i = N, призначте
    1. a [i + m] = b [i], a = перший масив, b = другий масив
  2. Сортувати перший масив
  3. Роздрукуйте необхідний результат

Впровадження рішення сортування масивів Leetcode Solution

Програма С ++

#include <bits/stdc++.h>
using namespace std;

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    for(int i = 0 ; i < n ; i++)
        a[i + m] = b[i];

    sort(a.begin() , a.end());
    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

Програма Java

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        for(int i = 0 ; i < n ; i++)
            a[i + m] = b[i];
        Arrays.sort(a);
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

Аналіз складності рішення відсортованих масивів з використанням літ-коду

Складність часу

O (KlogK), Де K = N + M. N = розмір першого масиву, M = розмір другого масиву. Оскільки ми сортуємо перший масив після того, як він зберігає всі N + M елементи.

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

O (1) як постійна пам'ять використовується для змінних.

Підхід (два покажчики)

Ми можемо використовувати двопоказник техніка об’єднання двох відсортованих масивів у новий масив. Але створення цього нового масиву буде коштувати додаткового місця. Ми можемо спробувати уникнути цього зайвого масиву, особливо коли перший масив має достатньо місця, щоб вмістити всі елементи обох масивів. Ми можемо використати два покажчики і розпочати об’єднання елементів у задній частині першого масиву.

Це вирішить проблему “зайвої пам’яті масиву”, оскільки ми продовжуємо фіксувати елементи у порожньому просторі.

Об’єднати сортовані масиви з розчином штрих-коду

Алгоритм

  1. Ініціалізуйте дві змінні i і j зберігання індексів останнього елемента першого та другого масиву відповідно.
    • i = M - 1, j = N - 1
  2. Ініціалізуйте змінну idx, зберігаючи останній індекс першого масиву, тобто:
    • idx = N + M - 1
  3. Тепер виконайте наступні дії до тих пір, поки не буде i or j стає нулем
    • Якщо a [i]> = b [j]
      • Призначити a [idx] = a [i], зменшити i
    • Ще
      • Призначити a [idx] = b [j], зменшити j
    • Поважність idx
  4. Будь-який з них i або j не дорівнює нулю, що означає, що деякі елементи ще мають бути об’єднані. Оскільки вони вже були б відсортовані, ми просто додаємо їх до першого масиву спереду.
  5. У той час як i не стає нулем,
    1. Призначити a [idx] = a [i]
    2. Поважність idx і i
  6. У той час як j не стає нулем,
    1. Призначити a [idx] = b [j]
    2. Поважність idx і j
  7. Тепер перший масив має всі елементи у необхідному відсортованому порядку.

Впровадження рішення сортування масивів Leetcode Solution

Програма С ++

#include <bits/stdc++.h>
using namespace std;

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    int i = m - 1 , j = n - 1 , idx = m + n - 1;
    while(i >= 0 && j >= 0)
    {
        if(a[i] >= b[j])
        {
            a[idx] = a[i];
            i--;
        }
        else
        {
            a[idx] = b[j];
            j--;
        }
        idx--;
    }


    while(i >= 0)
        a[idx--] = a[i--];

    while(j >= 0)
        a[idx--] = b[j--];

    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

Програма Java

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        int i = m - 1 , j = n - 1 , idx = m + n - 1;
        while(i >= 0 && j >= 0)
        {
            if(a[i] >= b[j])
            {
                a[idx] = a[i];
                i--;
            }
            else
            {
                a[idx] = b[j];
                j--;
            }
            idx--;
        }

        while(i >= 0)
            a[idx--] = a[i--];

        while(j >= 0)
            a[idx--] = b[j--];

        return;
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

Аналіз складності рішення відсортованих масивів з використанням літ-коду

Складність часу

O (N + M). N = розмір першого масиву, M = розмір другого масиву. Коли ми обходимо обидва масиви один раз.

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

O (1), оскільки ми зберігаємо всі елементи в першому масиві. Отже, алгоритм є на місці.