Միաձուլել տեսակավորված զանգվածների Leetcode լուծումը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon խնձոր Bloomberg ByteDance Cisco eBay Expedia facebook Goldman Sachs-ը Google IBM LinkedIn lyft Microsoft Netflix Պատգամախոս սեղան Uber VMware Անտաշ անասուն նողկալի արարած Yandex
Դասավորություն Երկու ցուցիչ

«Միավորել տեսակավորված զանգվածները» խնդրում մեզ տրվում է երկու զանգվածներ տեսակավորված է ոչ նվազման կարգով: Առաջին զանգվածը լրիվ լրացված չէ և ունի բավականաչափ տարածք `երկրորդ զանգվածի բոլոր տարրերը տեղավորելու համար: Մենք պետք է միաձուլենք երկու զանգվածները, այնպես, որ առաջին զանգվածը պարունակի ինչպես զանգվածների տարրեր, այնպես էլ դասավորված լինի ոչ իջնող պատվիրել

Օրինակ

{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 լուծույթի բարդության վերլուծություն

Timeամանակի բարդություն

O (KlogK), Որտեղ K = N + M, N = առաջին զանգվածի չափը, M = երկրորդ զանգվածի չափը: Երբ մենք դասավորում ենք առաջին զանգվածը այն բանից հետո, երբ այն պահպանում է N + M բոլոր տարրերը:

Տիեզերական բարդություն

Ո (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. Այժմ առաջին զանգվածն ունի բոլոր տարրերը ըստ պահանջվող դասավորվածության:

Միաձուլել տեսակավորված զանգվածների 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 լուծույթի բարդության վերլուծություն

Timeամանակի բարդություն

O (N + M). N = առաջին զանգվածի չափը, M = երկրորդ զանգվածի չափը: Երբ մենք միանգամից անցնում ենք երկու զանգվածները:

Տիեզերական բարդություն

O (1), երբ մենք պահում ենք բոլոր տարրերը առաջին զանգվածում: Այսպիսով, ալգորիթմն է տեղում.