Сұрыпталған массивтерді біріктіру Leetcode Solution


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма Bloomberg ByteDance Cisco еВау Expedia Facebook Голдман Сакс Google IBM LinkedIn lyft Microsoft Netflix Oracle үстел қиятын VMware Yahoo Яндекс
Array Екі көрсеткіш

«Біріктірілген сұрыпталған массивтерді біріктіру» проблемасында бізге екі берілген массивтер кемімейтін ретпен сұрыпталған. Бірінші массив толығымен толтырылмаған және екінші массивтің барлық элементтерін орналастыруға жеткілікті орынға ие. Бірінші жиым екі массивтің де элементтерін қамтитын және сұрыпталатындай екі массивті біріктіруіміз керек төмендемейтін тапсырыс.

мысал

{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 шешімін енгізу

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 Solution

Уақыттың күрделілігі

O (KlogK), мұндағы K = N + M. N = бірінші массивтің өлшемі, M = екінші массивтің өлшемі. Бірінші жиымды барлық N + M элементтерін сақтағаннан кейін сұрыптайтын болсақ.

Ғарыштың күрделілігі

O (1) өйткені тұрақты жады айнымалылар үшін қолданылады.

Тәсіл (екі нұсқағыш)

Біз пайдалана аламыз екі көрсеткіш жаңа сұрыпталған екі массивті біріктіру әдістемесі. Бірақ бұл жаңа массивті құру қосымша орын қажет етеді. Біз бұл қосымша массивтен аулақ болуға тырыса аламыз, әсіресе бірінші жиым екі массивтің барлық элементтерін ұстауға жеткілікті орынға ие болған кезде. Біз екі көрсеткішті пайдаланып, бірінші массивтің артындағы элементтерді біріктіре бастаймыз.

Бұл бос кеңістіктегі элементтерді түзетуді жалғастыра отырып, «қосымша массивтік жады» мәселесін шешеді.

Сұрыпталған массивтерді біріктіру Leetcode Solution

Алгоритм

  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 Solution

Уақыттың күрделілігі

O (N + M). N = бірінші массивтің өлшемі, M = екінші массивтің өлшемі. Екі массивті де бір рет айналып өткенде.

Ғарыштың күрделілігі

O (1), өйткені біз барлық элементтерді бірінші массивте сақтаймыз. Сонымен, алгоритм бұл орында.