አንጻራዊ ድርድር ድርድር Leetcode መፍትሔ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ዴ ሻው eBay google የ Microsoft
ሰልፍ ሃሽ ማፕ መደርደር

በዚህ ችግር ውስጥ ሁለት ተሰጠን ድርድሮች የአዎንታዊ ቁጥሮች የሁለተኛው ድርድር ሁሉም አካላት የተለዩ ናቸው እናም በመጀመሪያው ድርድር ውስጥ ይገኛሉ። ሆኖም ፣ የመጀመሪያው ድርድር በሁለተኛው ድርድር ውስጥ የሌሉ የተባዙ አባሎችን ወይም አባሎችን ይይዛል ፡፡

የመጀመሪያውን ድርድር መደርደር እና የሁለተኛውን ድርድር ልክ እንደ ንጥረ ነገሮቹን አንጻራዊ ቅደም ተከተል በመያዝ መመለስ አለብን። በሁለተኛው ድርድር ውስጥ የሌሉ ንጥረነገሮች በማያልቅ ሁኔታ በድርድሩ መጨረሻ ላይ መታየት አለባቸው ፡፡ በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ከ 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

ማስረጃሁለተኛውን ድርድር እንደ ተመሳሳይ ቅደም ተከተል እንዲይዙ የመጀመሪያውን ረድፍ እንደገና እንመድባለን ፡፡

አቀራረብ (ብጁ ንፅፅር)

ማንኛውንም የማጣሪያ ዘዴ ስንጠቀም አንጻራዊ ቅደም ተከተላቸውን ለመወሰን በአንድ ድርድር ሁለት እሴቶች መካከል ንፅፅሮችን እንጠቀማለን። ለምሳሌ ፣ በአረፋ ዓይነት ትንሹ ንጥረ ነገር በምድቡ ውስጥ ወደፊት እንዲመጣ ሁለት ተጓዳኝ አባሎችን ማወዳደር እንቀጥላለን ፡፡ የ “ታናሽ” ፍቺ የሚመጣው ከአካላት ስፋት ወይም እሴት ነው። በአጠቃላይ ‹‹››››››››››››››› ‹››››››››››››››››››››››››››››››››››› Mid n’ime‹ ‹‹X›››››››››››››››››› ያንሳል የ RHS እሴት። የፕሮግራም አወጣጥ ቋንቋዎች እነዚህ ኦፕሬተሮች እንዲሆኑ እንድናሻሽል ያስችሉናል ከመጠን በላይ ተጭኗል በተፈላጊ መንገዶች ፡፡ እዚህ የምንጠቀመው ይህንን ነው ፡፡ ትዕዛዙን ለመወሰን የተለያዩ የንፅፅር ዘዴዎችን የምንጠቀምባቸው እንደዚህ ያሉ የፕሮግራም አወጣጥ ስልቶች ብጁ ማወዳደር ተብሎ ይጠራል እናም ብጁ ንፅፅሮችን በመጠቀም እናሳካለን ፡፡

እኛ በምንፈልገው ፋሽን ውስጥ ያሉትን ነገሮች ለማወዳደር በሚያስችለን በአይነት ተግባር ውስጥ ሌላ ክርክር እናልፋለን ፡፡ አጠቃላይ አሠራሩን ለመረዳት የሚከተሉትን ኮድ እንፈትሽ-

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

ከላይ ባለው ኮድ ቅንጥስ ውስጥ ፣ ንፅፅሩ አንድ እሴት መሆኑን ይፈትሻል አንደኛ ከእሴት በፊት መምጣት አለበት ሁለተኛ በኢንቲጀር ድርድር ማነፃፀሪያው መመለስ አለበት እውነተኛ ከፈለግን አንደኛ በፊት እንዲመጣ ሁለተኛ. አለበለዚያ እኛ እንመለሳለን የሐሰት. ከላይ ያለው ኮድ በቅደም ተከተል ቅደም ተከተልን በቅደም ተከተል የምንመድብበት ምሳሌ ነው ፡፡ በተመሳሳይ ፣ በጃቫ ውስጥ ሀ ንፅፅር () ለእሱ የተላለፉትን ሁለት ክርክሮች ቅደም ተከተል ለመወሰን ክፍል። እሱ በመመለስ የ 3-መንገድ ንፅፅርን ያከናውን -1 ፣ 0 እና 1. ከሆነ አንደኛ ክርክር ከሱ ያነሰ ነው ሁለተኛ፣ ይመለሳል -1. አለበለዚያ የመጀመሪያው ክርክር ከሁለተኛው የሚበልጥ ከሆነ ይመለሳል 1. 0፣ ካልሆነ።

አልጎሪዝም

  1. ሃሽ ካርታን ያስጀምሩ ቦታ <> በሁለተኛው ድርድር ውስጥ የንጥሎች ጠቋሚዎችን ወደየየራሳቸው አመላካቾች ለመሰብሰብ
  2. የመጀመሪያውን ድርድር ደርድር ፣ ግን የንፅፅር ተግባርን በማለፍ (በ C ++ ውስጥ ላምዳዳ ተግባርን በመጠቀም ወይም በጃቫ ውስጥ ንፅፅር <> በይነገጽ በመጠቀም)
  3. ማነፃፀሪያው በሁለት እሴቶች ላይ ይሠራል አንደኛ ሁለተኛ እንደሚከተለው:
    1. If አቋም [መጀመሪያ]አቀማመጥ [ሰከንድ] የለም
      1. ትንሹ አካል መጀመሪያ እንዲመጣ እንፈልጋለን ፣ ስለዚህ ተመለሱ መጀመሪያ <ሰከንድ
    2. If አቋም [መጀመሪያ] የለም:
      1. እንመለሳለን የሐሰት as አንደኛ በድርድሩ ውስጥ በኋላ መምጣት አለበት
    3. If አቀማመጥ [ሰከንድ] የለም:
      1. ተመለስ እውነተኛ
    4. ተመለስ አቀማመጥ [መጀመሪያ] <አቀማመጥ [ሁለተኛ]
  4. ውጤቱን ያትሙ

አንጻራዊ የዝርዝር ድርድር Leetcode መፍትሄ ተግባራዊነት

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

የዘመድ ድርድር ቅደም ተከተሎች ዝርዝር ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ከፍተኛ (NlogN ፣ M)) የት N = የመጀመሪያው ድርድር መጠን እና M = የሁለተኛው ድርድር መጠን። የ O (M) ጊዜ የሚወስድ ሁለተኛ ረድፍ ላይ አንድ ነጠላ ማለፊያ እናካሂዳለን እና ንፅፅሩ በቋሚነት የሚከናወን መሆኑን ከግምት በማስገባት የኦ (NlogN) ጊዜ የሚወስድ የመጀመሪያውን ድርድር እንመድባለን ፡፡

የቦታ ውስብስብነት

ኦ (ኤም) የሁለተኛው ድርድር ንጥረ ነገሮችን ጠቋሚዎችን በሃሽ ካርታ ውስጥ ስናስቀምጥ ፡፡

አቀራረብ (የመቁጠር ድርድር)

ድርድር 1 = {1, 2, 2, 2} እና ድርድር 2 = {2, 1} ን እንውሰድ። ሁለተኛውን ድርድር ማቋረጥ ይጀምሩ። መጀመሪያ ቁጥር 2 እንመለከታለን። 3 2 ቶች እንደነበሩ ብናውቅ ከድርድር መረጃ ጠቋሚ 1. ጀምሮ እነዚህን እሴቶች በቀላል 0 ውስጥ በቀላሉ እንፅፋቸው ነበር ፣ ከዚያ ፣ በድርድር 1 ውስጥ ኢንቲጀር 2 አለን። እንደገና ፣ ድግግሞሹን የምናውቅ ቢሆን ኖሮ በቀላሉ ከሁለት ከሁለት በኋላ ባስቀመጥናቸው ነበር ፡፡ በተመሣሣይ ሁኔታ ፣ በአራይ 1 ውስጥ ያሉትን ሁሉንም ንጥረ ነገሮች ድግግሞሾችን ማከማቸት እና በመቀጠል በአራ 2 ውስጥ ያሉትን ንጥረ ነገሮች እንደ ድግግሞሾቻቸው እንደገና በመጻፍ አንድ ድርድርን አንድ ድርድርን ማስኬድ እንችላለን ፡፡

ግን ከዚያ በኋላም ቢሆን በአድር 1 ውስጥ የሚገኙትን ግን በድርድር ውስጥ የማይገኙትን አካላት ችላ ማለት ነው ፡፡ ስለዚህ ፣ ጥቂት ድግግሞሽ የሚቀረው እያንዳንዱን ንጥረ ነገር ከዝቅተኛ ወሰን ወደ ላይኛው ወሰን መፈተሻ እናካሂዳለን እና ወደ ድርድር 2 ይፃፉ ፡፡ ከዝቅተኛው ወሰን ወደ ላይ ስለምንሄድ እነዚህን “ተጨማሪ” ንጥረ ነገሮችን ባልቀነሰ ሁኔታ እንመድባቸዋለን።

አልጎሪዝም

  1. ድርድርን ያስጀምሩ መደጋገም የመጠን 1000 በ Array1 እና ውስጥ የንጥሎች ድግግሞሾችን ለማከማቸት መታወቂያ እንደገና በድርድር 1 ውስጥ አባሎችን ለመጻፍ አቀማመጥ ለማወቅ።
  2. ለእያንዳንዱ ንጥረ ነገር በድርድር 2 ውስጥ
    • ቢሆንም ድግግሞሽ [i]> 0:
      • ድርድር ይመድቡ 1 [idx] = i
      • idx ++
      • ድግግሞሽ [i] -
  3. ለእያንዳንዱ ንጥረ ነገር i በክልሉ ውስጥ [0, 4000]:
    • ቢሆንም ድግግሞሽ [i]> 0:
      • ድርድር ይመድቡ 1 [idx] = i
      • idx ++
      • ድግግሞሽ [i] -
  4. ውጤቱን ያትሙ

አንጻራዊ የዝርዝር ድርድር Leetcode መፍትሄ ተግባራዊነት

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

የዘመድ ድርድር ቅደም ተከተሎች ዝርዝር ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ከፍተኛ (N ፣ M ፣ 1000)) ኦ (ኤን) ጊዜ በሚወስድ ሃሽ ካርታ ውስጥ የመጀመሪያውን ድርድር አባሎች ድግግሞሽን ስናስቀምጥ ፡፡ ከዚያ በሁለተኛው ድርድር ውስጥ ላሉት እያንዳንዱ ንጥረ ነገሮች ድግግሞሾቻቸው እስከ 0. እስከሚሆኑ ድረስ በመጀመሪያ ረድፍ ላይ መፃፋቸውን እንቀጥላለን ፣ በመጨረሻ እኛ ማንኛውንም የግራ አካል ለመሙላት በክልሉ ውስጥ ያለውን እያንዳንዱን ንጥረ ነገር [0 ፣ 4000] እንፈትሻለን ፡፡

የቦታ ውስብስብነት

ኦ (1) የንጥረ ነገሮችን ድግግሞሽ ለማስቀመጥ በዚህ ሁኔታ ከ (1000) ጋር እኩል የሆነ ቋሚ ቦታ እንደምንጠቀም ፡፡