सापेक्ष सॉर्ट ऐरे लेटकोड सॉल्यूशन  


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना डीई शॉ ईबे गूगल माइक्रोसॉफ्ट
एल्गोरिदम ऐरे कोडिंग हैश मैप साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस छंटाई

इस समस्या में, हमें दो दिए गए हैं सरणियों सकारात्मक पूर्णांकों की। दूसरे सरणी के सभी तत्व अलग हैं और पहले सरणी में मौजूद हैं। हालाँकि, पहले सरणी में डुप्लिकेट तत्व या ऐसे तत्व हो सकते हैं जो दूसरे सरणी में नहीं हैं।

हमें पहले एरे को सॉर्ट करना होगा और उसके एलीमेंट्स के रिलेटिव ऑर्डर को दूसरे एरे में वैसा ही रखते हुए वापस करना होगा। तत्व जो दूसरे सरणी में मौजूद नहीं हैं, उन्हें सरणी के अंत में गैर-घटते तरीके से दिखाई देना चाहिए। सरणी में तत्व 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;
});

उपरोक्त कोड स्निपेट में, तुलनित्र जांचता है कि क्या एक मूल्य है प्रथम मूल्य से पहले आना चाहिए दूसरा एक पूर्णांक सरणी में। तुलनित्र को वापस लौट जाना चाहिए <strong>उद्देश्य</strong> अगर हम चाहें प्रथम पहले आना दूसरा। नहीं तो हम लौटते हैं असत्य। उपरोक्त कोड एक चित्रण है जहां हम सरणी को घटते क्रम में क्रमबद्ध करते हैं। इसी तरह, जावा में, हम एक का उपयोग करते हैं तुलनित्र () दो तर्कों के आदेश को तय करने के लिए कक्षा इसे पारित की गई। यह -3, 1, और 0. लौटाकर 1-तरफ़ा तुलना करता है प्रथम तर्क से कम है दूसरा, यह लौटता है -1। यदि पहला तर्क दूसरे से अधिक है, तो यह वापस आ जाता है 1. , अन्यथा।

कलन विधि

  1. एक हैश मानचित्र को प्रारंभ करें स्थिति <> दूसरे सरणी में तत्वों के सूचकांकों को उनके संबंधित सूचकांकों तक पहुंचाने के लिए
  2. पहले सरणी को क्रमबद्ध करें, लेकिन एक तुलनित्र फ़ंक्शन (C ++ में लैम्बडा फ़ंक्शन का उपयोग करके या जावा में तुलनित्र <> इंटरफ़ेस के साथ)
  3. तुलनित्र दो मूल्यों पर काम करता है प्रथम और दूसरा के रूप में इस प्रकार है:
    1. If स्थिति [पहली] और स्थिति [दूसरा] मौजूद नहीं है:
      1. हम चाहते हैं कि छोटा तत्व पहले आए, इसलिए वापस लौटें पहला <दूसरा
    2. If स्थिति [पहली] मौजूद नहीं है:
      1. हम लौटते हैं असत्य as प्रथम बाद में सरणी में आना चाहिए
    3. If स्थिति [दूसरा] मौजूद नहीं है:
      1. वापसी <strong>उद्देश्य</strong>
    4. वापसी स्थिति [पहली] <स्थिति [दूसरी]
  4. परिणाम प्रिंट करें

सापेक्ष सॉर्ट ऐरे लेटकोड सॉल्यूशन का कार्यान्वयन

C ++ प्रोग्राम

#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) समय लगता है तुलनात्मक समय में प्रदर्शन किया जाता है।

यह भी देखें
जांचें कि क्या यह एक सीधी रेखा लेटकोड समाधान है

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

ओ (एम) जैसा कि हम दूसरे सरणी के तत्वों के सूचकांक को हैश मैप में संग्रहीत करते हैं।

दृष्टिकोण (प्रकार की गणना)  

मान लें Array1 = {1, 2, 2, 2} और Array2 = {2, 1}। दूसरे ऐरे को ट्रेस करना शुरू करें। हम पूर्णांक 2 पहले देखते हैं। अगर हमें पता था कि 3 2 थे तो हमने आसानी से इंडेक्स 1. से शुरू होने वाले Array0 में इन मानों को लिखा होगा। फिर, हमारे पास Array1 में पूर्णांक 2 है। फिर से, अगर हमें इसकी आवृत्ति पता थी, तो हम आसानी से उन्हें दोहों के बाद संग्रहीत कर सकते थे। इसी तरह, हम Array1 में सभी तत्वों की आवृत्तियों को संग्रहीत कर सकते हैं और फिर Array2 में एकल पास चला सकते हैं, Array1 में तत्वों को उनकी आवृत्तियों के अनुसार फिर से लिख सकते हैं।

लेकिन उसके बाद भी, हम उन तत्वों को अनदेखा कर रहे हैं जो Array1 में नहीं बल्कि Array2 में मौजूद हैं। इसलिए, हम प्रत्येक तत्व के लिए निचली सीमा से ऊपरी सीमा की जाँच के लिए एक लूप चलाते हैं जिसकी कुछ आवृत्ति बची है और इसे Array1 में लिखें। चूंकि हम निचली सीमा से ऊपरी तक जाते हैं, इसलिए हम इन "अतिरिक्त" तत्वों को गैर-घटते हुए तरीके से छांट रहे होंगे।

कलन विधि

  1. एक सरणी आरंभ करें: आवृत्ति आकार का 1000 Array1 में तत्वों की आवृत्तियों को संग्रहीत करने के लिए और IDX Array1 में फिर से तत्वों को लिखने की स्थिति जानने के लिए।
  2. हर तत्व के लिए Array2 में:
    • जबकि आवृत्ति [i]> 0:
      • Array1 [idx] = i असाइन करें
      • idx ++
      • आवृत्ति [i] -
  3. हर तत्व के लिए i सीमा में: [0, 4000]:
    • जबकि आवृत्ति [i]> 0:
      • Array1 [idx] = i असाइन करें
      • idx ++
      • आवृत्ति [i] -
  4. परिणाम प्रिंट करें

सापेक्ष सॉर्ट ऐरे लेटकोड सॉल्यूशन का कार्यान्वयन

C ++ प्रोग्राम

#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

सापेक्ष सॉर्ट ऐरे लेटकोड सॉल्यूशन की जटिलता विश्लेषण

समय जटिलता

ओ (अधिकतम (एन, एम, 1000)) जैसा कि हम हे (एन) समय लेने वाले हैश मैप में पहले सरणी के तत्वों की आवृत्ति को संग्रहीत करते हैं। फिर दूसरे एरे में प्रत्येक तत्व के लिए, हम उन्हें पहले एरे में लिखते रहते हैं जब तक कि उनकी आवृत्तियाँ 0. नहीं हो जाती हैं। आखिर में, हम किसी भी लेफ्ट एलिमेंट को भरने के लिए रेंज [0, 4000] में हर एलिमेंट की जांच करते हैं।

यह भी देखें
शून्य लिटकोड समाधान के लिए एक संख्या को कम करने के लिए कदमों की संख्या

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

ओ (1) जैसा कि हम निरंतर स्थान का उपयोग करते हैं जो तत्वों की आवृत्ति को संग्रहीत करने के लिए इस मामले में ओ (1000) के बराबर है।