متعلقہ ترتیب سرنی لیٹکوڈ حل


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ڈی ای شا ای بے گوگل مائیکروسافٹ
لڑی ہش میپ چھانٹ

اس پریشانی میں ، ہمیں دو دیا جاتا ہے صفیں مثبت عدد کا۔ دوسری صف کے تمام عناصر الگ الگ ہیں اور پہلی صف میں موجود ہیں۔ تاہم ، پہلی صف میں ڈپلیکیٹ عناصر یا عناصر شامل ہوسکتے ہیں جو دوسری صف میں نہیں ہیں۔

ہمیں پہلی صف کو ترتیب دینے کی ضرورت ہے اور اس کے عناصر کی نسبتی ترتیب کو اسی طرح رکھتے ہوئے اسے واپس کرنا ہے جو دوسرے صف میں ہے۔ وہ عناصر جو دوسرے صف میں موجود نہیں ہیں ان کو کم نہ ہونے والے انداز میں صف کے آخر میں پیش ہونا چاہئے۔ صف میں موجود عناصر 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 ، اور XNUMX ہیں جن کو عدم استحکام کے لحاظ سے ترتیب دیا گیا ہے۔

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

وضاحت: ہم پھر پہلی صف کو اس طرح ترتیب دیتے ہیں کہ اب اس کے عناصر بھی اسی طرح کی ترتیب میں ہیں جیسے دوسرے صف میں۔

نقطہ نظر (کسٹم موازنہ)

جب ہم چھانٹنے کا کوئی طریقہ استعمال کرتے ہیں تو ، ہم ان کے متعلقہ حکم کا فیصلہ کرنے کے لئے کسی صف کی دو اقدار کے موازنہ استعمال کرتے ہیں۔ مثال کے طور پر ، بلبلا ترتیب میں ، ہم دو ملحقہ عناصر کا موازنہ کرتے رہتے ہیں تاکہ چھوٹے عنصر کو صف میں آگے لایا جاسکے۔ "چھوٹے" کی تعریف عناصر کی وسعت یا قدر سے ہوتی ہے۔ عام طور پر ، '<' آپریٹر چیک کرتا ہے کہ LHS کی قدر ہے سے کم ہے RHS قدر. پروگرامنگ کی زبانیں ہمیں ان آپریٹرز کو تبدیل کرنے کی اجازت دیتی ہیں بہت زیادہ مطلوبہ طریقوں سے۔ یہ وہی ہے جو ہم یہاں استعمال کریں گے۔ پروگرامنگ کی ایسی تکنیک جہاں ہم آرڈرنگ کا فیصلہ کرنے کے لئے موازنہ کے مختلف طریقے استعمال کرتے ہیں اسے کسٹم موازنہ کہا جاتا ہے اور ہم اپنی مرضی کے تقابلیوں کا استعمال کرکے اسے حاصل کرتے ہیں۔

ہم ترتیب دیں فنکشن میں ایک اور دلیل پاس کرتے ہیں جو ہمیں کسی بھی فیشن میں عناصر کا موازنہ کرنے کے قابل بناتا ہے۔ اس کے عمومی کام کو سمجھنے کے ل us ، آئیے مندرجہ ذیل کوڈ کو چیک کریں:

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. نتیجہ پرنٹ کریں

متعلقہ ترتیب والے سرے لیٹکوڈ حل کا نفاذ

سی ++ پروگرام

#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) وقت کو مانتے ہوئے موازنہ مستقل وقت میں انجام دیا جاتا ہے۔

خلائی پیچیدگی

O (M) چونکہ ہم ہیش کے نقشے میں دوسری صف کے عناصر کے اشارے جمع کرتے ہیں۔

نقطہ نظر (گنتی ترتیب)

آرا 1 = {1 ، 2 ، 2 ، 2} اور ارے 2 = {2 ، 1 ass فرض کرنے دیں۔ دوسری صف کو عبور کرنا شروع کریں۔ ہم سب سے پہلے عددی 2 دیکھتے ہیں۔ اگر ہمیں معلوم ہوتا کہ 3 2 ہیں تو ہم اشاریہ 1 سے شروع ہونے والے اری 0 میں یہ اقدار آسانی سے لکھتے ہیں۔ پھر ، ہمارے پاس ارے 1 میں عددی نمبر 2 ہے۔ ایک بار پھر ، اگر ہمیں اس کی تعدد معلوم ہوتی ، تو ہم انھیں آسانی سے دو بار کے بعد اسٹور کرلیتے۔ اسی طرح ، ہم تمام عناصر کی فریکوئینسی کو ارے 1 میں اسٹور کرسکتے ہیں اور پھر ارای 2 کے ایک پاس کو چلا سکتے ہیں ، ان کے تعدد کے مطابق ارے 1 میں عناصر کو دوبارہ لکھ سکتے ہیں۔

لیکن اس کے بعد بھی ، ہم ان عناصر کو نظرانداز کریں گے جو اری ون میں موجود ہیں لیکن ارے 1 میں نہیں ہیں۔ لہذا ، ہم ہر عنصر کی جانچ کرنے کے لئے نیچے کی حد سے اوپر کی حد تک جانچ کرتے ہوئے لوپ چلاتے ہیں جس میں کچھ تعدد باقی رہ جاتا ہے اور اسے ارے 2 میں لکھتے ہیں۔ چونکہ ہم نچلی حد سے اوپر کی طرف جاتے ہیں ، لہذا ہم ان "اضافی" عناصر کو کم کرتے ہوئے انداز میں ترتیب دیتے ہیں۔

الگورتھم

  1. ایک صف شروع کریں: فریکوئنسی سائز کا 1000 ارے 1 اور میں عناصر کی تعدد کو اسٹور کرنے کے لئے idx دوبارہ سرنی 1 میں عناصر لکھنے کی پوزیشن کو جاننے کے ل.
  2. ہر عنصر کے لئے صف میں 2:
    • جبکہ تعدد [i]> 0:
      • ارے 1 [idx] تفویض کریں = i
      • idx ++
      • تعدد [i] -
  3. ہر عنصر کے لئے i حد میں: [0 ، 4000]:
    • جبکہ تعدد [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) وقت لینے والے ہیش میپ میں پہلی صف کے عناصر کی تعدد کو اسٹور کرتے ہیں۔ پھر دوسری صف میں موجود ہر عنصر کے ل we ، ہم انہیں پہلی صف میں لکھتے رہتے ہیں یہاں تک کہ ان کی تعدد 0 ہوجاتی ہے۔ آخر میں ، ہم کسی بھی بائیں عنصر کو بھرنے کے لئے رینج [0 ، 4000] میں ہر عنصر کی جانچ پڑتال کرتے ہیں۔

خلائی پیچیدگی

O (1) چونکہ ہم اس وقت عناصر کی تعدد کو اسٹور کرنے کے لئے مستقل جگہ استعمال کرتے ہیں جو O (1000) کے برابر ہے۔