Адноснае рашэнне сартавання масіва


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка DE Шоу eBay Google Microsoft
масіў 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

Тлумачэнне: Мы зноў сартуем першы масіў так, каб яго элементы зараз знаходзіліся ў аналагічным парадку, як у другім масіве.

Падыход (нестандартны кампаратар)

Калі мы выкарыстоўваем любы спосаб сартавання, мы выкарыстоўваем параўнанне двух значэнняў масіва, каб вызначыць іх адносны парадак. Напрыклад, пры бурбавальнай сартаванні мы працягваем параўноўваць два суседнія элементы, каб меншы элемент можна было перанесці ў масіў. Вызначэнне "меншы" паходзіць ад велічыні ці значэння элементаў. Увогуле, аператар '<' правярае значэнне LHS менш значэнне RHS. Мовы праграмавання дазваляюць нам змяняць гэтыя аператары перагружаны пажаданымі спосабамі. Гэта тое, што мы тут будзем выкарыстоўваць. Такія метады праграмавання, пры якіх мы выкарыстоўваем розныя метады параўнання, каб прыняць рашэнне аб упарадкаванні, называюцца індывідуальным параўнаннем, і мы дасягаем яго з дапамогай карыстацкіх кампаратараў.

Мы перадаем яшчэ адзін аргумент у функцыі сартавання, які дазваляе нам параўноўваць элементы любым спосабам, які мы хочам. Каб зразумець яго агульнае функцыянаванне, давайце праверым наступны код:

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

У прыведзеным вышэй фрагменце кода кампаратар правярае, ці ёсць значэнне 1. павінна стаяць перад значэннем 2. у цэлалікавым масіве. Параўнальны кампанент павінен вярнуцца праўда калі мы хочам 1. прыйсці раней 2.. У адваротным выпадку мы вяртаемся ілжывы. Прыведзены вышэй код - ілюстрацыя, калі мы сартуем масіў у парадку змяншэння. Аналагічна, у Java мы выкарыстоўваем Параўнальнік () клас, каб вырашыць парадак перадачы яму двух аргументаў. Ён выконвае трохбаковае параўнанне, вяртаючы -3, 1 і 0. Калі 1. аргумент менш, чым 2., ён вяртаецца -1. У адваротным выпадку, калі першы аргумент большы за другі, ён вяртаецца 1. 0, у адваротным выпадку.

Алгарытм

  1. Ініцыялізацыя хэш-карты пазіцыя <> хэшаваць індэксы элементаў у другім масіве да адпаведных індэксаў
  2. Сартаванне першага масіва, але з перадачай функцыі кампаратара (з выкарыстаннем лямбда-функцыі ў C ++ або інтэрфейсу comparator <> у Java)
  3. Кампаратар працуе па двух значэннях 1. і 2. наступным чынам:
    1. If пазіцыя [першая] і пазіцыя [другая] не існуе:
      1. Мы хочам, каб меншы элемент быў першым, таму вярніцеся першы <другі
    2. If пазіцыя [першая] не існуе:
      1. Мы вяртаемся ілжывы as 1. павінна прыйсці пазней у масіве
    3. If пазіцыя [другая] не існуе:
      1. Вяртаць праўда
    4. Вяртаць пазіцыя [першая] <пазіцыя [другая]
  4. Раздрукуйце вынік

Рэалізацыя рашэння адноснага сартавання Leetcode Solution

Праграма 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, мы б лёгка запісалі гэтыя значэнні ў Array1, пачынаючы з індэкса 0. Затым у 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. Раздрукуйце вынік

Рэалізацыя рашэння адноснага сартавання Leetcode Solution

Праграма 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), у гэтым выпадку захоўваем частату элементаў.