সাজানো অ্যারেগুলি লেটকোড সমাধানটি মার্জ করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ByteDance সিসকো ইবে এক্সপিডিয়া ফেসবুক গোল্ডম্যান শ্যাস গুগল আইবিএম লিঙ্কডইন Lyft মাইক্রোসফট Netflix এর আকাশবাণী মনের উপরে স্পষ্ট ছবির ন্যায় ছাপ উবার অথবা VMware নরপশু ইয়ানডেক্স
বিন্যাস দুই পয়েন্টার

"মার্জ করা বাছাই করা অ্যারে" সমস্যায় আমাদের দুটি দেওয়া হয় অ্যারে ক্রমহীন ক্রম অনুসারে বাছাই করা। প্রথম অ্যারে পুরোপুরি পূরণ করা হয় না এবং দ্বিতীয় অ্যারের সমস্ত উপাদানগুলিকেও সমন্বিত করার জন্য পর্যাপ্ত জায়গা রয়েছে। আমাদের দুটি অ্যারে একত্রীকরণ করতে হবে, যেমন প্রথম অ্যারেতে উভয় অ্যারের উপাদান থাকে এবং এতে সাজানো হয় অবরোহহীন অর্ডার।

উদাহরণ

{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 = প্রথম অ্যারে, খ = দ্বিতীয় অ্যারে
  2. প্রথম অ্যারে বাছাই করুন
  3. প্রয়োজনীয় ফলাফল মুদ্রণ করুন

মার্জ সাজানো অ্যারেগুলি লেটকোড সমাধানের প্রয়োগ

সি ++ প্রোগ্রাম

#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

মার্জ করা বাছাই করা অ্যারেগুলি লেটকোড সমাধানের জটিলতা বিশ্লেষণ

সময় জটিলতা

O (KlogK), কোথায় কে = এন + এম। প্রথম অ্যারের এন = আকার, দ্বিতীয় অ্যারের এম = আকার। যেহেতু আমরা প্রথম অ্যারেটিকে সমস্ত এন + এম উপাদানগুলি সংরক্ষণ করার পরে বাছাই করি।

স্পেস জটিলতা ity

ও (1) ধ্রুবক মেমরি হিসাবে চলক জন্য ব্যবহৃত হয়।

পদ্ধতির (দুটি পয়েন্টার)

আমরা ব্যবহার করতে পারি দ্বি-পয়েন্টার দু'টি সাজানো অ্যারেটিকে নতুন অ্যারেতে মার্জ করার কৌশল তবে, এই নতুন অ্যারে তৈরি করতে অতিরিক্ত জায়গার ব্যয় হবে। আমরা এই অতিরিক্ত অ্যারেটি এড়াতে চেষ্টা করতে পারি বিশেষত যখন প্রথম অ্যারেতে উভয় অ্যারের সমস্ত উপাদান ধরে রাখতে পর্যাপ্ত জায়গা থাকে। আমরা দুটি পয়েন্টার ব্যবহার করতে পারি এবং প্রথম অ্যারের পিছনে উপাদানগুলি মার্জ করা শুরু করতে পারি।

এটি "অতিরিক্ত অ্যারে মেমরি" এর সমস্যাটি কেটে দেবে কারণ আমরা শূন্য স্থানে উপাদানগুলি ঠিক করতে থাকি।

সাজানো অ্যারেগুলি লেটকোড সমাধানটি মার্জ করুন

অ্যালগরিদম

  1. দুটি ভেরিয়েবল শুরু করুন i এবং j যথাক্রমে প্রথম এবং দ্বিতীয় অ্যারের শেষ উপাদানটির সূচকগুলি সংরক্ষণ করে।
    • i = এম - 1, জে = এন - 1
  2. একটি পরিবর্তনশীল সূচনা আইডিএক্স, প্রথম অ্যারের শেষ সূচকটি সংরক্ষণ করে, এটি হল:
    • আইডিএক্স = এন + এম - 1
  3. এখন, উভয় না হওয়া পর্যন্ত নিম্নলিখিতটি করুন i or j শূন্য হয়ে যায়
    • যদি একটি [i]> = বি [জে]
      • একটি [আইডিএক্স] = একটি [আই], হ্রাস অর্পণ করুন i
    • আর
      • হ্রাস, একটি [আইডিএক্স] = বি [জে] বরাদ্দ করুন j
    • হ্রাস আইডিএক্স
  4. হয় i বা j শূন্য নয়, যার অর্থ কিছু উপাদান এখনও একীভূত হতে পারে। যেহেতু তারা ইতিমধ্যে সাজানো পদ্ধতিতে থাকবে, আমরা কেবল তাদের সামনের প্রথম অ্যারেটিতে যুক্ত করব।
  5. যদিও i শূন্য হয় না,
    1. একটি [idx] = একটি [i] বরাদ্দ করুন
    2. হ্রাস আইডিএক্স এবং i
  6. যদিও j শূন্য হয় না,
    1. একটি [idx] = বি [জে] বরাদ্দ করুন
    2. হ্রাস আইডিএক্স এবং j
  7. এখন প্রথম অ্যারেটিতে প্রয়োজনীয় সাজানো ক্রমে সমস্ত উপাদান রয়েছে।

মার্জ সাজানো অ্যারেগুলি লেটকোড সমাধানের প্রয়োগ

সি ++ প্রোগ্রাম

#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

মার্জ করা বাছাই করা অ্যারেগুলি লেটকোড সমাধানের জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন + এম). N প্রথম অ্যারের আকার = M = দ্বিতীয় অ্যারের আকার। আমরা উভয় অ্যারে একবার অতিক্রম করার সময়।

স্পেস জটিলতা ity

ও (1), যেহেতু আমরা প্রথম অ্যারেতে সমস্ত উপাদান সংরক্ষণ করি। সুতরাং, অ্যালগরিদম হয় জায়গায়.