Ҳалли массиви нисбии Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon DE Шо мехаранд Google Microsoft
тартиботи ҳарбӣ HashMap Sorting

Дар ин мушкилот, ба мо дуто медиҳанд массиви ададҳои мусбат. Ҳама унсурҳои массиви дуюм фарқ мекунанд ва дар массиви аввал мавҷуданд. Аммо, массиви аввал метавонад унсурҳои такрорӣ ё унсурҳое дошта бошад, ки дар массиви дуюм нестанд.

Мо бояд массиви аввалро ҷобаҷо кунем ва онро бо тартиби нисбии унсурҳояш нигоҳ дошта, тавре ки дар массиви дуюм ҷойгиранд, баргардонем. Элементҳое, ки дар массиви дуюм мавҷуд нестанд, бояд дар охири массив ба тарзи камшаванда пайдо шаванд. Элементҳои массив аз арзиши 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;
});

Дар порчаи коди дар боло овардашуда, компаратор оё арзишро месанҷад аввал бояд пеш аз арзиш биёяд дуюм дар массиви бутун Компартор бояд баргардад ҳақиқӣ агар мо хоҳем аввал пеш омадан дуюм. Дар акси ҳол, мо бармегардем бардурӯғ. Рамзи дар боло овардашуда мисолест, ки мо массивро бо тартиби камшумор ҷобаҷо мекунем. Ба ҳамин монанд, дар Java, мо a -ро истифода мебарем Муқоиса () синф барои муайян кардани тартиби ду далели ба он додашуда. Он муқоисаи 3-ро бо роҳи бозгашти -1, 0 ва 1 иҷро мекунад. Агар аввал далел камтар аз дуюм, он бармегардад -1. Дар акси ҳол, агар далели аввал аз дуюм зиёдтар бошад, он бармегардад 1. 0, дар акси ҳол.

Алгоритм

  1. Харитаи ҳешро оғоз кунед мавқеъ <> ба нишондиҳандаҳои унсурҳои массиви дуюм ба нишондиҳандаҳои дахлдори онҳо хэш кунанд
  2. Массиви аввалро ҷобаҷо кунед, аммо бо гузаштани функсияи компаратор (бо истифодаи функсияи лямбда дар C ++ ё интерфейси компартор <> дар Java)
  3. Муқоиса дар ду арзиш кор мекунад аввал ва дуюм таври зерин:
    1. If мавқеъ [аввал] ва мавқеъ [дуюм] вуҷуд надорад:
      1. Мо мехоҳем, ки унсури хурдтар аввал биёяд, пас баргардед аввал <дуюм
    2. If мавқеъ [аввал] вуҷуд надорад:
      1. Мо бармегардем бардурӯғ as аввал бояд баъдтар дар массив омада расад
    3. If мавқеъ [дуюм] вуҷуд надорад:
      1. бозгашт ҳақиқӣ
    4. бозгашт мавқеъ [аввал] <мавқеъ [дуюм]
  4. Натиҷаро чоп кунед

Татбиқи Solution Array нисбии Solution 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;
}

Барномаи Java

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

Таҳлили мураккабии ҳалли массиви нисбии Solution Leetcode

Мураккабии вақт

O (максимум (NlogN, M)) ки дар N = андозаи массиви аввал ва M = андозаи массиви дуюм. Мо дар массиви дуюм як гузаришро иҷро мекунем, ки вақти O (M) -ро мегирад ва массиви аввалро, ки вақти O (NlogN) -ро мегирад, бо назардошти муқоиса дар вақти доимӣ, ҷудо мекунем.

Мураккабии фазо

О (М) вақте ки мо нишондиҳандаҳои унсурҳои массиви дуюмро дар харитаи хэш нигоҳ медорем.

Равиш (Ҳисобкунии навъ)

Бигзор Array1 = {1, 2, 2, 2} ва Array2 = {2, 1}. Гузариши массиви дуюмро оғоз кунед. Дар аввал мо адади 2-ро мебинем. Агар мо медонистем, ки 3 2 буданд, мо ин арзишҳоро ба осонӣ дар Array1 сар карда аз индекси 0 менавиштем. Пас, дар Array1 адади 2 дорем. Боз ҳам, агар мо басомади онро медонистем, пас аз дугона онҳоро ба осонӣ нигоҳ медоштем. Ба ҳамин монанд, мо метавонем басомади ҳамаи элементҳоро дар Array1 нигоҳ дорем ва сипас гузариши ягонаи Array2 –ро иҷро карда, элементҳоро дар Array1 мувофиқи басомадҳояшон дубора нависем.

Аммо ҳатто пас аз он, мо он унсурҳоро, ки дар Array1 мавҷуданд, вале дар Array2 надорем, нодида мегирем. Ҳамин тавр, мо аз лимити поёнӣ то лимити боло давраеро барои ҳар як элементе, ки басомади каме боқӣ мондааст, месанҷем ва онро ба Array1 менависем. Азбаски мо аз лимити поёнӣ ба боло боло мебарем, мо ин унсурҳои "изофӣ" -ро ба тариқи бетанаффус ҷудо мекунем.

Алгоритм

  1. Массивро оғоз кунед: басомад андозаи 1000 барои нигоҳ доштани басомадҳои элементҳо дар Array1 ва idx донистани мавқеи навиштани унсурҳо дар Array1 боз.
  2. Барои ҳар як унсур дар Array2:
    • ҳол он басомади [ман]> 0:
      • Array1 [idx] = i -ро таъин кунед
      • idx ++
      • басомад [i] -
  3. Барои ҳар як унсур i дар диапазони: [0, 4000]:
    • ҳол он басомади [ман]> 0:
      • Array1 [idx] = i -ро таъин кунед
      • idx ++
      • басомад [i] -
  4. Натиҷаро чоп кунед

Татбиқи Solution Array нисбии Solution 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;
}

Барномаи Java

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

Таҳлили мураккабии ҳалли массиви нисбии Solution Leetcode

Мураккабии вақт

O (макс (N, M, 1000)) чунон ки мо басомади унсурҳои массиви аввалро дар харитаи хэш бо назардошти вақти O (N) нигоҳ медорем. Пас барои ҳар як унсури массиви дуюм, мо онҳоро дар массиви аввал менависем, то басомадҳояшон 0 шавад. Дар ниҳоят, мо ҳар як унсури диапазони [0, 4000] -ро пур мекунем, ки ягон элементи чапро пур кунанд.

Мураккабии фазо

О (1) зеро мо фазои доимиро, ки ба O (1000) баробар аст, дар ин ҳолат барои нигоҳ доштани басомади элементҳо истифода мебарем.