සාපේක්ෂ වර්ග කිරීම අරාව ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් ඩී ෂෝ ඊ බේ ගූගල් මයික්රොසොෆ්ට්
අරා හැෂ්මැප් වර්ග කිරීම

මෙම ගැටලුවේදී අපට දෙකක් ලබා දී ඇත අරා ධනාත්මක නිඛිලවල. දෙවන අරාවෙහි සියලුම අංග එකිනෙකට වෙනස් වන අතර පළමු අරාවෙහි පවතී. කෙසේ වෙතත්, පළමු අරාවෙහි දෙවන අරාවෙහි නොමැති අනුපිටපත් මූලද්‍රව්‍ය හෝ මූලද්‍රව්‍ය අඩංගු විය හැකිය.

අපි පළමු අරාව වර්ග කර එහි මූලද්‍රව්‍යයන්ගේ සාපේක්ෂ අනුපිළිවෙල දෙවන අරාවෙහි ඇති ආකාරයටම නැවත ලබා දිය යුතුය. දෙවන අරාවෙහි නොමැති මූලද්‍රව්‍යයන් අරාව අවසානයේ අඩු නොවන ආකාරයෙන් දිස්විය යුතුය. අරාවෙහි ඇති මූලද්‍රව්‍යයන් 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 වේ. එබැවින්, ඒවා පළමුව ප්‍රති result ල අරාවෙහි දිස් වේ. අනෙක් මූලද්‍රව්‍ය 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. පළමු අරාව වර්ග කරන්න, නමුත් සංසන්දනාත්මක ශ්‍රිතයක් පසු කිරීමත් සමඟ (C ++ හි ලැම්බඩා ශ්‍රිතය භාවිතා කිරීම හෝ ජාවාහි සංසන්දක <> අතුරු මුහුණත භාවිතා කිරීම)
  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) කාලය ගතවන පළමු අරාව වර්ග කරන්න.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (එම්) අපි දෙවන අරාවෙහි මූලද්‍රව්‍යයන්ගේ දර්ශක හැෂ් සිතියමක ගබඩා කරන විට.

ප්‍රවේශය (වර්ග කිරීම ගණන් කිරීම)

Array1 = {1, 2, 2, 2} සහ Array2 = {2, 1 උපකල්පනය කරමු. දෙවන අරාව හරහා ගමන් කිරීම ආරම්භ කරන්න. අපි මුලින්ම පූර්ණ සංඛ්‍යා 2 දකිමු. 3 2 ක් ඇති බව අප දැන සිටියේ නම්, මෙම අගයන් 1 වන දර්ශකයේ සිට අරේ 0 හි පහසුවෙන් ලිවීමට ඉඩ තිබුණි. එවිට, අපට අරේ 1 හි පූර්ණ සංඛ්‍යා 2 ඇත. නැවතත්, අපි එහි සංඛ්‍යාතය දැන සිටියා නම්, අපි ඒවා දෙකෙන් පසුව පහසුවෙන් ගබඩා කර තබන්නෙමු. ඒ හා සමානව, අපට Array1 හි ඇති සියලුම මූලද්‍රව්‍යයන්ගේ සංඛ්‍යාත ගබඩා කර Array2 හි එක් මුරපදයක් ධාවනය කර, Array1 හි මූලද්‍රව්‍ය ඒවායේ සංඛ්‍යාත අනුව නැවත ලිවිය හැකිය.

නමුත් ඉන් පසුව පවා, අපි අරේ 1 හි ඇති නමුත් අරේ 2 හි නොමැති මූලද්‍රව්‍ය නොසලකා හරිනු ඇත. එබැවින්, යම් සංඛ්‍යාතයක් ඉතිරිව ඇති සෑම මූලද්‍රව්‍යයක් සඳහාම අපි පහළ සීමාවේ සිට ඉහළ සීමාව දක්වා ලූපයක් ධාවනය කර එය 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. ප්‍රති .ලය මුද්‍රණය කරන්න

සාපේක්ෂ වර්ගීකරණ අරා ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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)) O (N) කාලය ගතවන හැෂ් සිතියමක පළමු අරාවේ මූලද්‍රව්‍ය සංඛ්‍යාතය ගබඩා කරන විට. දෙවන අරාවෙහි සෑම මූලද්‍රව්‍යයක් සඳහාම, ඒවායේ සංඛ්‍යාත 0 බවට පත්වන තෙක් අපි ඒවා පළමු අරාවෙහි ලියා තබන්නෙමු. අවසානයේදී, ඕනෑම වම් මූලද්‍රව්‍යයක් පිරවීම සඳහා [0, 4000] පරාසයේ ඇති සෑම මූලද්‍රව්‍යයක්ම අපි පරීක්ෂා කරමු.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1) මූලද්‍රව්‍යයන්ගේ සංඛ්‍යාතය ගබඩා කිරීම සඳහා අපි මෙම අවස්ථාවේදී O (1000) ට සමාන නියත අවකාශයක් භාවිතා කරන බැවින්.