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


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon խնձոր Bloomberg ByteDance Cisco eBay Expedia facebook Goldman Sachs-ը Google IBM LinkedIn lyft Microsoft Netflix Պատգամախոս սեղան Uber VMware Անտաշ անասուն նողկալի արարած Yandex
ալգորիթմները Դասավորություն կոդավորում հարցազրույց հարցազրույցի պատրաստում 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. Տպեք պահանջվող արդյունքը

Միաձուլել տեսակավորված զանգվածների 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 լուծումըPin

Ալգորիթմ

  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 = երկրորդ զանգվածի չափը: Երբ մենք միանգամից անցնում ենք երկու զանգվածները:

Տես նաեւ,
Չորս Leetcode լուծման հզորություն

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

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