मिलाइएको क्रमबद्ध एर्रे लीटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल ब्लूमबर्ग बाइटडेन्स सिस्को eBay Expedia फेसबुक Goldman सैक्स गुगल आईबीएम LinkedIn lyft माइक्रोसफ्ट 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. आवश्यक परिणाम प्रिन्ट गर्नुहोस्

मर्ज क्रमबद्ध एर्रेको लेटकोड समाधानको कार्यान्वयन

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

मर्ज क्रमबद्ध एर्रेको लेटकोड समाधानको जटिलता विश्लेषण

समय जटिलता

O (KlogK)जहाँ K = N + M। N = पहिलो एर्रेको आकार, दोस्रो एर्रेको M = आकार। हामीले पहिलो एरे क्रमबद्ध गरे पछि यसले सबै N + M एलिमेन्टहरू भण्डारण गरिसकेका छन।

ठाउँ जटिलता

O (१) स्थिर चल मेमोरी भ्यारीएबलका लागि प्रयोग भएको हुनाले

दृष्टिकोण (दुई पोइन्टर्स)

हामी प्रयोग गर्न सक्छौं दुई-सूचक दुई क्रमबद्ध एर्रेलाई नयाँ एरेमा मर्ज गर्न टेक्निक। तर, यो नयाँ एर्रेको सिर्जनाको लागि अतिरिक्त स्थान खर्च हुनेछ। हामी यो अतिरिक्त एरेबाट बच्न कोशिस गर्न सक्छौं विशेष गरी जब पहिलो एरेमा दुबै एर्रेको सबै एलिमेन्टहरू राख्न पर्याप्त ठाउँ हुन्छ। हामी दुई सूचकहरू प्रयोग गर्न सक्दछौं र एर्रेन्सलाई पहिलो एर्रेको पछाडि मर्ज गर्न सक्दछौं।

यसले "अतिरिक्त एरे मेमोरी" को समस्यालाई काट्नेछ किनकि हामी शून्य ठाउँमा एलिमेन्टहरू फिक्स गरिरहन्छौं।

मिलाइएको क्रमबद्ध एर्रे लीटकोड समाधान

अल्गोरिदम

  1. दुई भ्यारीएबल सुरू गर्नुहोस् ij क्रमश: पहिलो र दोस्रो एर्रेको अन्तिम तत्वको सूचकांक भण्डारण गर्दै।
    • i = M - १, j = N - १
  2. भ्यारीएबल शुरुवात गर्नुहोस् आईडीएक्स, पहिलो एर्रेको अन्तिम अनुक्रमणिका भण्डारण गर्दै, त्यो हो:
    • idx = N + M - १
  3. अब, कुनै एक सम्म निम्न गर्नुहोस् i or j शून्य हुन्छ
    • यदि एक [i]> = b [j]
      • एक [idx] = a [i], घटाउनुहोस् i
    • एल्स
      • एक [idx] = b [j], घटाउनुहोस् j
    • घट आईडीएक्स
  4. कि त म वा जे शून्य होईन, जसको मतलब केहि तत्त्वहरू अझै मर्ज गर्न बाँकी छ। किनकि उनीहरू पहिले नै क्रमबद्ध ढ be्गले हुने थियो, हामी त्यसलाई अगाडिको पहिलो एर्रेमा थप्दछौं।
  5. जबकि i शून्य हुँदैन,
    1. एक [idx] = a [i] तोक्नुहोस्
    2. घट आईडीएक्सi
  6. जबकि j शून्य हुँदैन,
    1. एक [idx] = b [j] तोक्नुहोस्
    2. घट आईडीएक्सj
  7. अब पहिलो एर्रेमा सबै एलिमेन्टहरू छन् क्रमबद्ध गरिएको अर्डरमा।

मर्ज क्रमबद्ध एर्रेको लेटकोड समाधानको कार्यान्वयन

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

मर्ज क्रमबद्ध एर्रेको लेटकोड समाधानको जटिलता विश्लेषण

समय जटिलता

O (N + M). N = पहिलो एर्रेको आकार, M = दोस्रो एर्रेको आकार। जब हामी दुबै एर्रे एकपटक ट्रान्सभर्स गर्दछौं।

ठाउँ जटिलता

O (१), हामी पहिलो एर्रेमा सबै एलिमेन्टहरू भण्डार गर्छौं। त्यसो भए एल्गोरिथ्म हो ठाउँमा.