Салыстырмалы массивтің Leitcode шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon DE Шоу еВау Google Microsoft
Array HashMap Сұрыптау

Бұл мәселеде бізге екі беріледі массивтер оң сандар. Екінші жиымның барлық элементтері ерекшеленеді және бірінші жиымда болады. Алайда, бірінші жиымда қайталанатын элементтер немесе екінші массивте жоқ элементтер болуы мүмкін.

Біз бірінші массивті сұрыптап, оны элементтерінің салыстырмалы ретін екінші жиымдағыдай сақтай отырып қайтаруымыз керек. Екінші жиымда жоқ элементтер массивтің соңында кемімейтін түрде пайда болуы керек. Массивтегі элементтер 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

Түсіндіру: Біз қайтадан бірінші массивті сұрыптаймыз, оның элементтері қазір екінші массивтегідей тәртіпті болады.

Тәсіл (Custom Comparator)

Кез-келген сұрыптау әдісін қолданған кезде, олардың салыстырмалы ретін анықтау үшін массивтің екі мәні арасындағы салыстыруды қолданамыз. Мысалы, көпіршікті сұрыптауда біз кішігірім элементті массивке шығаруға болатындай етіп, екі іргелес элементтерді салыстыра береміз. «Кішірек» анықтамасы элементтердің шамасынан немесе мәнінен шығады. Жалпы, '<' операторы 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-да біз а Компаратор () оған берілген екі аргументтің ретін шешетін сынып. Ол -3, 1 және 0 мәндерін қайтару арқылы 1 жақты салыстыруды орындайды. Егер бірінші аргумент секунд, ол оралады -1. Басқа жағдайда, егер бірінші аргумент екіншіден үлкен болса, ол қайтады 1. 0, әйтпесе.

Алгоритм

  1. Хэш картасын инициализациялаңыз позициясы <> екінші жиымдағы элементтердің индекстерін тиісті индекстерге хэштеу
  2. Бірінші массивті сұрыптаңыз, бірақ компаратор функциясын өткізе отырып (C ++ тіліндегі lambda функциясын немесе Java-да компаратор <> интерфейсін қолданып)
  3. Компаратор екі мән бойынша жұмыс істейді бірінші және секунд келесідей:
    1. If позиция [бірінші] және позиция [екінші] жоқ:
      1. Біз кішірек элементтің бірінші болғанын қалаймыз, сондықтан оралыңыз бірінші <екінші
    2. If позиция [бірінші] жоқ:
      1. Біз қайтамыз жалған as бірінші массивке кейінірек келуі керек
    3. If позиция [екінші] жоқ:
      1. қайтару шынайы
    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;
}

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

Салыстырмалы сұрыпты массивтің күрделілігін талдау Leetcode шешімі

Уақыттың күрделілігі

O (максимум (NlogN, M)) қайда N = бірінші массивтің өлшемі және M = екінші массивтің өлшемі. O (M) уақытын алатын екінші жиымға бір өтуді жүргіземіз және салыстыру тұрақты уақытта орындалады деп O (NlogN) уақытын алатын бірінші жиымды сұрыптаймыз.

Ғарыштың күрделілігі

O (M) біз екінші массив элементтерінің индексін хэш картасында сақтайтын болсақ.

Тәсіл (Сұрыптау)

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;
}

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

Салыстырмалы сұрыпты массивтің күрделілігін талдау Leetcode шешімі

Уақыттың күрделілігі

O (максимум (N, M, 1000)) біз бірінші жиым элементтерінің жиілігін хэш-картада O (N) уақытты сақтай отырып сақтаймыз. Содан кейін екінші жиымдағы әрбір элемент үшін біз оларды жиіліктер 0-ге айналғанға дейін бірінші массивте жаза береміз. Соңында [0, 4000] диапазонындағы кез-келген сол жақтағы элементтің толтырылуын тексереміз.

Ғарыштың күрделілігі

O (1) өйткені элементтердің жиілігін сақтау үшін бұл жағдайда O (1000) -ге тең тұрақты кеңістікті қолданамыз.