Относително сортиране на масив Leetcode решение


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка 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

Обяснение: Отново сортираме първия масив, така че неговите елементи сега са в подобен ред като този във втория масив.

Подход (персонализиран сравнител)

Когато използваме някакъв метод за сортиране, използваме сравнения между две стойности на масив, за да определим техния относителен ред. Например, при сортиране на балончета, ние продължаваме да сравняваме два съседни елемента, така че по-малкият елемент да може да бъде предвиден в масива. Определението за „по-малък“ идва от големината или стойността на елементите. По принцип операторът „<“ проверява дали 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. 0, в противен случай.

алгоритъм

  1. Инициализирайте хеш карта позиция <> да хешира индексите на елементите във втория масив към съответните им индекси
  2. Сортирайте първия масив, но с предаване на функция за сравнение (използвайки ламбда функция в C ++ или за сравнение <> интерфейс в Java)
  3. Сравнителят работи върху две стойности първи и втори , както следва:
    1. If позиция [първа] и позиция [втора] не съществува:
      1. Искаме по-малкият елемент да е на първо място, затова се върнете първо <второ
    2. If позиция [първа] не съществува:
      1. Връщаме се фалшив as първи трябва да дойде по-късно в масива
    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. След това имаме цяло число 1 в Array2. Отново, ако знаехме честотата му, щяхме лесно да ги съхраним след два. По подобен начин можем да съхраняваме честотите на всички елементи в Array1 и след това да изпълняваме един проход на Array2, като презаписваме елементите в Array1 според техните честоти.

Но дори и след това, ние бихме игнорирали онези елементи, които присъстват в Array1, но не и в Array2. И така, ние провеждаме цикъл от проверка на долната граница до горната граница за всеки елемент, който има някаква оставаща честота, и го записваме в Array1. Тъй като се изкачваме от долната граница към горната, бихме сортирали тези „допълнителни“ елементи по не намаляващ начин.

алгоритъм

  1. Инициализирайте масив: честота на размер 1000 за съхраняване на честоти на елементи в Array1 и idx за да се знае позицията за записване на елементи в Array1 отново.
  2. За всеки елемент в Array2:
    • Докато честота [i]> 0:
      • Присвояване на масив1 [idx] = i
      • idx ++
      • честота [i] -
  3. За всеки елемент i в диапазона: [0, 4000]:
    • Докато честота [i]> 0:
      • Присвояване на масив1 [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), в този случай за съхраняване на честотата на елементите.