Сорттолгон массивдерди Leetcode Solution менен бириктирүү  


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon алма Bloomberg ByteDance Cisco Окшош Expedia Facebook Goldman Sachs Гугл IBM LinkedIn Lyft Microsoft Netflix Oracle стол Uber VMware Yahoo Яндекс
Алгоритмы согуштук тизме коддоо интервью интервью даярдоо LeetCode LeetCodeSolutions Эки көрсөткүч

"Сортирленген массивдерди бириктирүү" көйгөйүндө экөөбүз берилген Arrays азайбай турган тартипте иреттелген. Биринчи массив толук толтурулган эмес жана экинчи массивдин бардык элементтерин батыра турган орун жетиштүү. Эки массивди бириктиришибиз керек, мисалы биринчи массив эки массивдин элементтерин камтыйт жана иргелет ылдый түшпөө токтому.

мисал  

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

Ыкма (Сорттоо)  

Экинчи массивдин бардык элементтерин биринчисине өткөрө алабыз. Андан кийин керектүү натыйжаны алуу үчүн биринчи массивди иреттей алабыз.

Algorithm

  1. I = 0ден i = Nге чейин, дайында
    1. a [i + m] = b [i], a = биринчи массив, b = экинчи массив
  2. Биринчи массивди иреттөө
  3. Керектүү натыйжаны басып чыгарыңыз

Бириктирилген иреттелген массивдерди Leetcode чечиминин ишке ашырылышы

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 Solution азайтуу String

Космостун татаалдыгы

O (1) өзгөрүлмө үчүн туруктуу эс тутуму колдонулат.

Мамиле (эки көрсөткүч)  

Биз колдоно алабыз эки көрсөткүч эки массивди жаңы массивге бириктирүү техникасы. Бирок, бул жаңы массивди түзүү кошумча орунду талап кылат. Биринчи массивде эки массивдин бардык элементтерин кармаганга жетиштүү орун болгондо, биз бул кошумча массивден алыс болууга аракет кыла алабыз. Эки көрсөткүчтү колдонуп, биринчи массивдин артындагы элементтерди бириктире баштасак болот.

Бош орундагы элементтерди оңдой берсек, бул "кошумча массивдин эс тутуму" көйгөйүн чечет.

Сорттолгон массивдерди Leetcode Solution менен бириктирүү

Algorithm

  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 чечиминин ишке ашырылышы

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), бардык элементтерди биринчи массивде сактаганыбыздай. Демек, алгоритм ушундай ордунда.