मर्ज सॉर्ट किए गए एरेस लेटकोड सॉल्यूशन


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना सेब ब्लूमबर्ग ByteDance सिस्को ईबे Expedia Facebook गोल्डमैन सैक्स गूगल आईबीएम लिंक्डइन Lyft माइक्रोसॉफ्ट नेटफ्लिक्स ओरेकल झाँकी 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. एक [i + m] = b [i], एक = पहला सरणी, 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), जहां के = एन + एम। पहले सरणी का N = आकार, दूसरे सरणी का M = आकार। जैसा कि हमने सभी एन + एम तत्वों को संग्रहीत करने के बाद पहली सरणी को सॉर्ट किया है।

अंतरिक्ष जटिलता

ओ (1) चूंकि चर के लिए निरंतर मेमोरी का उपयोग किया जाता है।

दृष्टिकोण (दो बिंदु)

हम प्रयोग कर सकते हैं दो-सूचक दो सॉर्ट किए गए सरणियों को एक नए सरणी में मर्ज करने की तकनीक। लेकिन, इस नए एरे के निर्माण में अतिरिक्त जगह खर्च होगी। हम इस अतिरिक्त सरणी से बचने की कोशिश कर सकते हैं, खासकर जब पहले सरणी में दोनों सरणियों के सभी तत्वों को रखने के लिए पर्याप्त स्थान है। हम दो बिंदुओं का उपयोग कर सकते हैं और पहले सरणी के पीछे तत्वों को विलय करना शुरू कर सकते हैं।

यह "अतिरिक्त सरणी मेमोरी" की समस्या को काट देगा क्योंकि हम शून्य स्थान में तत्वों को ठीक करते रहते हैं।

मर्ज सॉर्ट किए गए एरेस लेटकोड सॉल्यूशन

कलन विधि

  1. प्रारंभिक दो चर i और j क्रमशः पहले और दूसरे सरणी के अंतिम तत्व के सूचकांकों को संग्रहीत करना।
    • i = M - 1, j = N - 1
  2. एक चर को प्रारंभ करें IDX, पहली सरणी का अंतिम सूचकांक, जो है:
    • idx = एन + एम - 1
  3. अब, निम्नलिखित में से किसी भी एक तक करें i or j शून्य हो जाता है
    • अगर एक [i]> = b [j]
      • [A idx] = a [i] असाइन करें i
    • अन्य
      • एक [आईडीएक्स] = बी [जे], डिक्रीमेंट सौंपें j
    • घटती IDX
  4. दोनों में से कोई मैं या जे शून्य नहीं है, जिसका अर्थ है कि कुछ तत्वों का विलय होना बाकी है। के रूप में वे पहले से ही एक तरह से किया जाएगा, हम बस उन्हें सामने वाले पहले सरणी में जोड़ते हैं।
  5. जबकि i शून्य नहीं बनता,
    1. [Idx] = a [i] असाइन करें
    2. घटती IDX और i
  6. जबकि j शून्य नहीं बनता,
    1. [Idx] = b [j] असाइन करें
    2. घटती IDX और 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 = दूसरी सरणी का आकार। जैसा कि हम दोनों सरणियों को एक बार पार करते हैं।

अंतरिक्ष जटिलता

ओ (1), जैसा कि हम सभी तत्वों को पहले सरणी में संग्रहीत करते हैं। तो, एल्गोरिथ्म है जगह में.