შერწყმა დახარისხებული მასივების Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Apple Bloomberg ByteDance Cisco eBay Expedia Facebook Goldman Sachs Google IBM LinkedIn ლიფტი microsoft Netflix Oracle ცხრილი Uber VMware Yahoo Yandex
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 Solution

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

ჯავა პროგრამა

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 ელემენტი.

სივრცის სირთულე

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]
      • დანიშნეთ [idx] = a [i], შემცირება i
    • სხვა
      • დანიშნეთ [idx] = b [j], შემცირება j
    • შემცირება idx
  4. არც ერთი მე ან ჯ არ არის ნულოვანი, რაც იმას ნიშნავს, რომ ზოგიერთი ელემენტი ჯერ კიდევ გაერთიანებულია. რადგან ისინი უკვე დახარისხებული წესით იქნებოდა, ჩვენ მათ უბრალოდ ვუერთებთ წინა მასივს.
  5. მიუხედავად იმისა, i არ ხდება ნულოვანი,
    1. მიანიჭეთ [idx] = a [i]
    2. შემცირება idx და i
  6. მიუხედავად იმისა, j არ ხდება ნულოვანი,
    1. დანიშნეთ [idx] = b [j]
    2. შემცირება idx და j
  7. ახლა პირველ მასივს აქვს ყველა ელემენტი საჭირო დახარისხებული თანმიმდევრობით.

განხორციელების შერწყმა დახარისხებული მასივები Leetcode Solution

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

ჯავა პროგრამა

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 = მეორე მასივის ზომა. როგორც ჩვენ ერთხელ დავათვალიერებთ ორივე მასივს.

სივრცის სირთულე

O (1), როგორც ჩვენ ვინახავთ ყველა ელემენტს პირველ მასივში. ასე რომ, ალგორითმი არის ადგილზე.