క్రమబద్ధీకరించిన శ్రేణుల లీట్‌కోడ్ పరిష్కారాన్ని విలీనం చేయండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ ByteDance సిస్కో eBay Expedia ద్వారా <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గోల్డ్మన్ సాచ్స్ గూగుల్ IBM లింక్డ్ఇన్ లిఫ్ట్ మైక్రోసాఫ్ట్ నెట్ఫ్లిక్స్ ఒరాకిల్ పట్టిక ఉబెర్ 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. అవసరమైన ఫలితాన్ని ముద్రించండి

విలీనం క్రమబద్ధీకరించిన శ్రేణుల లీట్‌కోడ్ పరిష్కారం అమలు

సి ++ ప్రోగ్రామ్

#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) స్థిరమైన మెమరీ వేరియబుల్స్ కోసం ఉపయోగించబడుతుంది.

అప్రోచ్ (రెండు పాయింటర్లు)

మేము ఉపయోగించవచ్చు రెండు-పాయింటర్ రెండు క్రమబద్ధీకరించిన శ్రేణులను కొత్త శ్రేణిలో విలీనం చేసే సాంకేతికత. కానీ, ఈ కొత్త శ్రేణిని సృష్టించడానికి అదనపు స్థలం ఖర్చవుతుంది. మొదటి శ్రేణికి రెండు శ్రేణుల యొక్క అన్ని అంశాలను ఉంచడానికి తగినంత స్థలం ఉన్నప్పుడు మేము ఈ అదనపు శ్రేణిని నివారించడానికి ప్రయత్నించవచ్చు. మేము రెండు పాయింటర్లను ఉపయోగించవచ్చు మరియు మొదటి శ్రేణి వెనుక భాగాలను విలీనం చేయడం ప్రారంభించవచ్చు.

మేము శూన్య స్థలంలో మూలకాలను పరిష్కరించేటప్పుడు ఇది “అదనపు శ్రేణి మెమరీ” యొక్క సమస్యను తగ్గిస్తుంది.

క్రమబద్ధీకరించిన శ్రేణుల లీట్‌కోడ్ పరిష్కారాన్ని విలీనం చేయండి

అల్గారిథం

  1. రెండు వేరియబుల్స్ ప్రారంభించండి i మరియు j మొదటి మరియు రెండవ శ్రేణి యొక్క చివరి మూలకం యొక్క సూచికలను వరుసగా నిల్వ చేస్తుంది.
    • i = M - 1, j = N - 1
  2. వేరియబుల్ ప్రారంభించండి idx, మొదటి శ్రేణి యొక్క చివరి సూచికను నిల్వ చేస్తుంది, అనగా:
    • idx = N + M - 1
  3. ఇప్పుడు, ఈ రెండింటిని ఈ క్రింది వరకు చేయండి i or j సున్నా అవుతుంది
    • ఒక [i]> = బి [జ] ఉంటే
      • [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. ఇప్పుడు మొదటి శ్రేణికి అవసరమైన క్రమబద్ధీకరించిన క్రమంలో అన్ని అంశాలు ఉన్నాయి.

విలీనం క్రమబద్ధీకరించిన శ్రేణుల లీట్‌కోడ్ పరిష్కారం అమలు

సి ++ ప్రోగ్రామ్

#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), మేము మొదటి శ్రేణిలోని అన్ని అంశాలను నిల్వ చేస్తున్నప్పుడు. కాబట్టి, అల్గోరిథం స్థానంలో.