Обединяване на сортирани масиви Leetcode решение  


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка ябълка Bloomberg ByteDance Cisco иБей Expedia Facebook Goldman Sachs Google IBM LinkedIn Lyft Microsoft Netflix Оракул Жива картина Uber VMware Yahoo Yandex
алгоритми Array кодиране Интервю интерпретация LeetCode LeetCodeSolutions Двупосочен

В проблема „Обединяване на сортирани масиви“ ни дават две масиви сортирани в низходящ ред. Първият масив не е напълно запълнен и има достатъчно място, за да побере и всички елементи от втория масив. Трябва да обединим двата масива, така че първият масив да съдържа елементи от двата масива и да бъде сортиран в не-низходящ поръчка.

Пример  

{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. Отпечатайте необходимия резултат

Внедряване на Merge Sorted Arrays Leetcode Solution

Програма C ++

#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

Анализ на сложността на решение за сортиране на сортирани масиви Leetcode

Сложност във времето

O (KlogK), Където K = N + M. N = размер на първия масив, M = размер на втория масив. Докато сортираме първия масив, след като той е съхранил всички N + M елементи.

Вижте също
Увеличаване на намаляващ низ Leetcode решение

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

O (1) тъй като постоянната памет се използва за променливи.

Подход (два указателя)  

Ние можем да използваме двупосочен техника за обединяване на двата сортирани масива в нов масив. Но създаването на този нов масив ще струва допълнително пространство. Можем да се опитаме да избегнем този допълнителен масив, особено когато първият масив има достатъчно място, за да побере всички елементи на двата масива. Можем да използваме два указателя и да започнем да обединяваме елементите в задната част на първия масив.

Това ще намали проблема с „допълнителната памет на масива“, докато продължаваме да фиксираме елементите в празното пространство.

Обединяване на сортирани масиви Leetcode решениещифт

алгоритъм

  1. Инициализирайте две променливи i и j съхраняване на индекси на последния елемент на първия и втория масив съответно.
    • i = M - 1, j = N - 1
  2. Инициализирайте променлива idx, съхраняващ последния индекс на първия масив, т.е.
    • idx = N + M - 1
  3. Сега направете следното, докато някой от i or j става нула
    • Ако a [i]> = b [j]
      • Присвояване на [idx] = a [i], декремент i
    • Още
      • Присвояване на [idx] = b [j], декремент j
    • снижаване idx
  4. Всеки от тях i или j не е нула, което означава, че някои елементи тепърва ще бъдат обединени. Тъй като те вече биха били сортирани, ние просто ги добавяме към първия масив отпред.
  5. Докато i не става нула,
    1. Присвояване на [idx] = a [i]
    2. снижаване idx и i
  6. Докато j не става нула,
    1. Присвояване на [idx] = b [j]
    2. снижаване idx и j
  7. Сега първият масив има всички елементи в необходимия сортиран ред.

Внедряване на Merge Sorted Arrays Leetcode Solution

Програма C ++

#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

Анализ на сложността на решение за сортиране на сортирани масиви Leetcode

Сложност във времето

O (N + M). N = размер на първия масив, M = размер на втория масив. Докато прехвърляме и двата масива веднъж.

Вижте също
Сила на четири Leetcode разтвор

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

O (1), като съхраняваме всички елементи в първия масив. И така, алгоритъмът е на място.