సాపేక్ష క్రమబద్ధీకరణ అర్రే లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ డిఇ షా eBay గూగుల్ మైక్రోసాఫ్ట్
అర్రే హాష్ మ్యాప్ సార్టింగ్

ఈ సమస్యలో, మాకు రెండు ఇవ్వబడ్డాయి శ్రేణుల సానుకూల పూర్ణాంకాల. రెండవ శ్రేణి యొక్క అన్ని అంశాలు విభిన్నమైనవి మరియు మొదటి శ్రేణిలో ఉంటాయి. ఏదేమైనా, మొదటి శ్రేణి రెండవ శ్రేణిలో లేని నకిలీ అంశాలు లేదా మూలకాలను కలిగి ఉంటుంది.

మేము మొదటి శ్రేణిని క్రమబద్ధీకరించాలి మరియు దాని మూలకాల యొక్క సాపేక్ష క్రమాన్ని రెండవ శ్రేణిలో మాదిరిగానే ఉంచాలి. రెండవ శ్రేణిలో లేని అంశాలు శ్రేణి చివరిలో తగ్గకుండా కనిపిస్తాయి. శ్రేణిలోని అంశాలు 1000 విలువను మించవు.

ఉదాహరణ

Array1 = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99}
Array2 = {5 , 6 , 12}
5 5 6 6 12 1 4 4 7 99

వివరణ: రెండవ శ్రేణిలోని మూలకాల క్రమం 5,6 మరియు 12. కాబట్టి, అవి ఫలిత శ్రేణిలో మొదట కనిపిస్తాయి. ఇతర అంశాలు 1, 4, 4, 7 మరియు 99, ఇవి తగ్గని క్రమంలో క్రమబద్ధీకరించబడతాయి.

Array1 = {5 , 4 , 3 , 2 , 1}
Array2 = {1 , 2 , 3 , 4 , 5}
1 2 3 4 5

వివరణ: మేము మళ్ళీ మొదటి శ్రేణిని క్రమబద్ధీకరిస్తాము, దాని మూలకాలు ఇప్పుడు రెండవ శ్రేణిలో మాదిరిగానే ఉంటాయి.

అప్రోచ్ (కస్టమ్ కంపారిటర్)

మేము ఏదైనా సార్టింగ్ పద్ధతిని ఉపయోగించినప్పుడు, శ్రేణి యొక్క రెండు విలువల మధ్య పోలికలను వాటి సాపేక్ష క్రమాన్ని నిర్ణయించడానికి ఉపయోగిస్తాము. ఉదాహరణకు, బబుల్ క్రమబద్ధీకరణలో, మేము రెండు ప్రక్కనే ఉన్న మూలకాలను పోల్చుకుంటాము, తద్వారా శ్రేణిలో చిన్న మూలకాన్ని ముందుకు తీసుకురావచ్చు. “చిన్నది” యొక్క నిర్వచనం మూలకాల పరిమాణం లేదా విలువ నుండి వచ్చింది. సాధారణంగా, LHS విలువ ఉంటే '<' ఆపరేటర్ తనిఖీ చేస్తుంది తక్కువ RHS విలువ. ప్రోగ్రామింగ్ లాంగ్వేజెస్ ఈ ఆపరేటర్లను సవరించడానికి మాకు అనుమతిస్తాయి ఓవర్లోడ్ కావాల్సిన మార్గాల్లో. దీనినే మనం ఇక్కడ ఉపయోగిస్తాం. ఆర్డరింగ్‌ను నిర్ణయించడానికి మేము వేర్వేరు పోలిక పద్ధతులను ఉపయోగించే ఇటువంటి ప్రోగ్రామింగ్ పద్ధతులను కస్టమ్ కంపారింగ్ అంటారు మరియు కస్టమ్ కంపారిటర్లను ఉపయోగించి దాన్ని సాధిస్తాము.

క్రమబద్ధీకరణ ఫంక్షన్‌లో మనం మరొక వాదనను పాస్ చేస్తాము, అది మనకు కావలసిన ఫ్యాషన్‌లోని అంశాలను పోల్చడానికి వీలు కల్పిస్తుంది. దాని సాధారణ పనితీరును అర్థం చేసుకోవడానికి, ఈ క్రింది కోడ్‌ను తనిఖీ చేద్దాం:

vector <int> a = {1 , 2 , 3 , 7 , 4};
sort(a.begin() , a.end() , [&](const int &first , const int &second){
    return first > second;
});

పై కోడ్ స్నిప్పెట్‌లో, పోలిక విలువ ఉందా అని తనిఖీ చేస్తుంది మొదటి విలువకు ముందు రావాలి రెండవ పూర్ణాంక శ్రేణిలో. పోలిక తిరిగి రావాలి నిజమైన మాకు కావాలంటే మొదటి ముందు రావడానికి రెండవ. లేకపోతే, మేము తిరిగి వస్తాము తప్పుడు. పై కోడ్ ఒక దృష్టాంతం, ఇక్కడ మేము శ్రేణిని క్రమబద్ధీకరించే క్రమంలో క్రమబద్ధీకరిస్తాము. అదేవిధంగా, జావాలో, మేము a కంపారిటర్ () దానికి పంపిన రెండు వాదనల క్రమాన్ని నిర్ణయించే తరగతి. ఇది -3, 1 మరియు 0 ని తిరిగి ఇవ్వడం ద్వారా 1-మార్గం పోలికను చేస్తుంది. ఉంటే మొదటి కంటే వాదన తక్కువ రెండవ, అది తిరిగి వస్తుంది -1. మొదటి వాదన రెండవదానికంటే ఎక్కువగా ఉంటే, అది తిరిగి వస్తుంది 1. 0, లేకపోతే.

అల్గారిథం

  1. హాష్ మ్యాప్‌ను ప్రారంభించండి స్థానం <> రెండవ శ్రేణిలోని మూలకాల సూచికలను వాటి సూచికలకు హాష్ చేయడానికి
  2. మొదటి శ్రేణిని క్రమబద్ధీకరించండి, కానీ కంపారిటర్ ఫంక్షన్‌ను పాస్ చేయడంతో (సి ++ లో లాంబ్డా ఫంక్షన్ లేదా జావాలో కంపారిటర్ <> ఇంటర్ఫేస్ ఉపయోగించి)
  3. కంపారిటర్ రెండు విలువలపై పనిచేస్తుంది మొదటి మరియు రెండవ ఈ క్రింది విధంగా:
    1. If స్థానం [మొదటి] మరియు స్థానం [రెండవ] ఉనికి లేకపోవుట:
      1. చిన్న మూలకం మొదట రావాలని మేము కోరుకుంటున్నాము, కాబట్టి తిరిగి వెళ్ళు మొదటి <రెండవ
    2. If స్థానం [మొదటి] ఉనికిలో లేదు:
      1. మేము తిరిగి వస్తాము తప్పుడు as మొదటి తరువాత శ్రేణిలో రావాలి
    3. If స్థానం [రెండవ] ఉనికిలో లేదు:
      1. రిటర్న్ నిజమైన
    4. రిటర్న్ స్థానం [మొదటి] <స్థానం [రెండవ]
  4. ఫలితాన్ని ముద్రించండి

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

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

#include <bits/stdc++.h>
using namespace std;

vector<int> relativeSortArray(vector<int>& Array1 , vector<int>& Array2)
{
    unordered_map <int , int> position;

    for(int i = 0 ; i < Array2.size() ; i++)
        position[Array2[i]] = i;

    sort(Array1.begin() , Array1.end() , [&](const int &first , const int &second)
     {
         if(position.find(first) == position.end() && position.find(second) == position.end())
             return first < second;
         if(position.find(first) == position.end())
             return false;
         if(position.find(second) == position.end())
             return true;
         return position[first] < position[second];
     });

    return Array1;
}

int main()
{
    vector <int> a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99} , b = {5 , 6 , 12};
    a = relativeSortArray(a , b);
    for(int &element : a)
        cout << element << " ";
    return 0;
}

జావా ప్రోగ్రామ్

import java.util.*;

class relative_sort
{
    public static void main(String args[])
    {
        int[] a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99};
        int[] b = {5 , 6 , 12};
        a = relativeSortArray(a , b);
        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }

    static int[] relativeSortArray(int[] Array1, int[] Array2) {
        Hashtable <Integer , Integer> position = new Hashtable<>();
        for(int i = 0 ; i < Array2.length ; i++)
            position.put(Array2[i] , i);

        Integer[] _Array1 = new Integer[Array1.length];
        for(int i = 0 ; i < _Array1.length ; i++)
            _Array1[i] = Array1[i];

        Arrays.sort(_Array1 , new Comparator<Integer>()
                    {
                        public int compare(Integer first , Integer second)
                        {
                            if(position.get(first) == null && position.get(second) == null)
                                return first - second;
                            if(position.get(first) == null)
                                return 1;
                            if(position.get(second) == null)
                                return -1;
                            return position.get(first) - position.get(second);
                        }
                    });

        for(int i = 0 ; i < Array1.length ; i++)
            Array1[i] = _Array1[i];
        return Array1;
    }
}
5 5 6 6 12 1 4 4 7 99

సాపేక్ష క్రమబద్ధీకరణ శ్రేణి లీట్‌కోడ్ పరిష్కారం యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (గరిష్టంగా (NlogN, M)) (ఇక్కడ N = మొదటి శ్రేణి యొక్క పరిమాణం మరియు M = రెండవ శ్రేణి యొక్క పరిమాణం. మేము రెండవ శ్రేణిలో ఒకే పాస్ను నడుపుతాము, ఇది O (M) సమయం తీసుకుంటుంది మరియు పోలిక స్థిరమైన సమయంలో జరుగుతుందని భావించి O (NlogN) సమయం తీసుకునే మొదటి శ్రేణిని క్రమబద్ధీకరిస్తుంది.

అంతరిక్ష సంక్లిష్టత

ఓ (మ) మేము రెండవ శ్రేణి యొక్క మూలకాల సూచికలను హాష్ మ్యాప్‌లో నిల్వ చేస్తున్నప్పుడు.

అప్రోచ్ (లెక్కింపు క్రమబద్ధీకరణ)

అర్రే 1 = {1, 2, 2, 2} మరియు అర్రే 2 = {2, 1 ume అనుకుందాం. రెండవ శ్రేణిని దాటడం ప్రారంభించండి. మేము మొదట పూర్ణాంకం 2 ని చూస్తాము. 3 2 లు ఉన్నాయని మనకు తెలిస్తే, ఇండెక్స్ 1 నుండి మొదలుపెట్టి అర్రే 0 లో ఈ విలువలను సులభంగా వ్రాస్తాము. అప్పుడు, మనకు అర్రే 1 లో పూర్ణాంకం 2 ఉంటుంది. మళ్ళీ, దాని పౌన frequency పున్యం మనకు తెలిస్తే, మేము వాటిని రెండు తర్వాత సులభంగా నిల్వచేస్తాము. ఇదే విధంగా, మేము అర్రే 1 లోని అన్ని మూలకాల యొక్క పౌన encies పున్యాలను నిల్వ చేసి, ఆపై అర్రే 2 యొక్క ఒకే పాస్ను అమలు చేయవచ్చు, అర్రే 1 లోని మూలకాలను వాటి పౌన .పున్యాల ప్రకారం తిరిగి వ్రాయవచ్చు.

కానీ ఆ తరువాత కూడా, అర్రే 1 లో ఉన్న అర్రే 2 లో లేని అంశాలను మేము విస్మరిస్తాము. కాబట్టి, కొంత పౌన frequency పున్యం మిగిలి ఉన్న ప్రతి మూలకం కోసం మేము తక్కువ పరిమితి నుండి ఎగువ పరిమితి వరకు ఒక లూప్‌ను నడుపుతాము మరియు దానిని అర్రే 1 లో వ్రాస్తాము. మేము తక్కువ పరిమితి నుండి పైకి వెళ్తున్నందున, మేము ఈ “అదనపు” అంశాలను తగ్గని రీతిలో క్రమబద్ధీకరిస్తాము.

అల్గారిథం

  1. శ్రేణిని ప్రారంభించండి: తరచుదనం పరిమాణం 1000 అర్రే 1 మరియు మూలకాల యొక్క పౌన encies పున్యాలను నిల్వ చేయడానికి idx అర్రే 1 లోని అంశాలను మళ్ళీ వ్రాయవలసిన స్థితిని తెలుసుకోవడానికి.
  2. ప్రతి మూలకం కోసం శ్రేణి 2 లో:
    • అయితే పౌన frequency పున్యం [i]> 0:
      • శ్రేణి 1 ను కేటాయించండి [idx] = i
      • idx ++
      • ఫ్రీక్వెన్సీ [i] -
  3. ప్రతి మూలకం కోసం i పరిధిలో: [0, 4000]:
    • అయితే పౌన frequency పున్యం [i]> 0:
      • శ్రేణి 1 ను కేటాయించండి [idx] = i
      • idx ++
      • ఫ్రీక్వెన్సీ [i] -
  4. ఫలితాన్ని ముద్రించండి

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

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

#include <bits/stdc++.h>
using namespace std;

vector <int> relativeSortArray(vector <int> &Array1 , vector <int> &Array2)
{
    vector <int> frequency(1010 , 0);
    for(int &x : Array1)
        frequency[x]++;

    int idx = 0;

    for(int &i : Array2)
    {
        while(frequency[i] > 0)
            Array1[idx++] = i , frequency[i]--;
    }

    for(int i = 0 ; i < 1010 ; i++)
        while(frequency[i] > 0)
            Array1[idx++] = i , frequency[i]--;

    return Array1;
}

int main()
{
    vector <int> a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99} , b = {5 , 6 , 12};
    a = relativeSortArray(a , b);
    for(int &element : a)
        cout << element << " ";
    return 0;
}

జావా ప్రోగ్రామ్

import java.util.*;

class relative_sort
{
    public static void main(String args[])
    {
        int[] a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99};
        int[] b = {5 , 6 , 12};
        a = relativeSortArray(a , b);
        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }

    static int[] relativeSortArray(int[] Array1 , int[] Array2)
    {
        int[] frequency = new int[1010];
        for(int i = 0 ; i < 1010 ; i++)
            frequency[i] = 0;

        for(int i = 0 ; i < Array1.length ; i++)
            frequency[Array1[i]]++;

        int idx = 0;

        for(int i = 0 ; i < Array2.length ; i++)
        {
            while(frequency[Array2[i]] > 0)
            {
                Array1[idx++] = Array2[i];
                frequency[Array2[i]]--;
            }
        }

        for(int i = 0 ; i < 1010 ; i++)
            while(frequency[i] > 0)
            {
                Array1[idx++] = i;
                frequency[i]--;
            }

        return Array1;
    }
}
5 5 6 6 12 1 4 4 7 99

సాపేక్ష క్రమబద్ధీకరణ శ్రేణి లీట్‌కోడ్ పరిష్కారం యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (గరిష్టంగా (N, M, 1000%)) O (N) సమయం తీసుకునే హాష్ మ్యాప్‌లో మొదటి శ్రేణి యొక్క మూలకాల ఫ్రీక్వెన్సీని మేము నిల్వ చేస్తున్నప్పుడు. రెండవ శ్రేణిలోని ప్రతి మూలకం కోసం, వాటి పౌన encies పున్యాలు 0 అయ్యే వరకు మేము వాటిని మొదటి శ్రేణిలో వ్రాస్తూనే ఉంటాము. చివరికి, ఏదైనా ఎడమ మూలకాన్ని పూరించడానికి మేము [0, 4000] పరిధిలోని ప్రతి మూలకాన్ని తనిఖీ చేస్తాము.

అంతరిక్ష సంక్లిష్టత

O (1) మూలకాల పౌన frequency పున్యాన్ని నిల్వ చేయడానికి ఈ సందర్భంలో O (1000) కు సమానమైన స్థిరమైన స్థలాన్ని మేము ఉపయోగిస్తాము.