Споји сортиране низове Леетцоде решење


Ниво тешкоће Лако
Често питани у адобе амазонка јабука Блоомберг БитеДанце Цисцо еБаи Екпедиа фацебоок Голдман Сакс гоогле ИБМ- ЛинкедИн лифт мицрософт Нетфлик пророчанство Таблеау Убер ВМваре иахоо иандек
Ред Тво Поинтер

У проблему „Спајање сортираних низова“ дата су нам два низови сортирано по неналазном редоследу. Први низ није у потпуности попуњен и има довољно простора да прими и све елементе другог низа. Морамо спојити два низа, тако да први низ садржи елементе оба низа и сортиран је у не-силазни поретка.

Пример

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

Приступ (сортирање)

Све елементе другог низа можемо пренети у први. Тада можемо сортирати први низ да бисмо добили тражени резултат.

Алгоритам

  1. За и = 0 до и = Н, доделите
    1. а [и + м] = б [и], а = први низ, б = други низ
  2. Сортирај први низ
  3. Одштампајте тражени резултат

Имплементација спајања сортираних низова Леетцоде решења

Програм Ц ++

#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;
}

Јава Програм

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

Анализа сложености обједињеног сортираног низа Леетцоде решење

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

О (КлогК), Где К = Н + М. Н = величина првог низа, М = величина другог низа. Док сортирамо први низ након што је сачувао све Н + М елементе.

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

О (1) како се за променљиве користи константна меморија.

Приступ (два показивача)

Можемо користити двострука техника спајања два сортирана низа у нови низ. Али, стварање овог новог низа коштаће додатни простор. Можемо покушати да избегнемо овај додатни низ, посебно када први низ има довољно простора да садржи све елементе оба низа. Можемо користити два показивача и започети спајање елемената на полеђини првог низа.

Ово ће смањити проблем „додатне меморије низа“ док стално поправљамо елементе у празнини.

Споји сортиране низове Леетцоде решење

Алгоритам

  1. Иницијализујте две променљиве i j чување индекса последњег елемента првог и другог низа.
    • и = М - 1, ј = Н - 1
  2. Иницијализујте променљиву идк, чување последњег индекса првог низа, то јест:
    • идк = Н + М - 1
  3. Сада, урадите следеће до било ког од i or j постаје нула
    • Ако је а [и]> = б [ј]
      • Додели декремент де [идк] = а [и] i
    • Друго
      • Доделите а [идк] = б [ј], декремент j
    • Декремент идк
  4. Било који и или ј није нула, што значи да неке елементе тек треба спојити. Како би већ били сортирани, једноставно их додамо првом низу испред.
  5. Док i не постаје нула,
    1. Доделите а [идк] = а [и]
    2. Декремент идк i
  6. Док j не постаје нула,
    1. Доделите а [идк] = б [ј]
    2. Декремент идк j
  7. Сада први низ има све елементе у траженом сортираном редоследу.

Имплементација спајања сортираних низова Леетцоде решења

Програм Ц ++

#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;
}

Јава Програм

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

Анализа сложености обједињеног сортираног низа Леетцоде решење

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

О (Н + М). N = величина првог низа, M = величина другог низа. Док једном прелазимо оба низа.

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

О (1), како смештамо све елементе у први низ. Дакле, алгоритам је на месту.