Рішення відносного масиву сортування Leetcode


Рівень складності Легко
Часто запитують у саман Амазонка Д. Е. Шоу 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;
});

У наведеному вище фрагменті коду порівняльник перевіряє, чи є значення перший має стояти перед значенням другий у цілочисельному масиві. Компаратор повинен повернутися правда якщо ми хочемо перший прийти раніше другий. В іншому випадку ми повертаємось false. Наведений вище код є ілюстрацією, де ми сортуємо масив у порядку зменшення. Подібним чином у Java ми використовуємо a Компаратор () клас, щоб визначити порядок передачі йому двох аргументів. Він виконує тристороннє порівняння, повертаючи -3, 1 та 0. Якщо перший аргумент менше, ніж другий, він повертається -1. В іншому випадку, якщо перший аргумент більший за другий, він повертається 1. 0, інакше.

Алгоритм

  1. Ініціалізуйте хеш-карту позиція <> хешувати індекси елементів у другому масиві до відповідних індексів
  2. Сортувати перший масив, але з передачею функції порівняння (з використанням лямбда-функції в C ++ або інтерфейсу comparator <> в Java)
  3. Порівняльник працює за двома значеннями перший і другий наступним чином:
    1. If позиція [перша] і позиція [друга] не існують:
      1. Ми хочемо, щоб менший елемент був на першому місці, тому повертаємо перший <другий
    2. If позиція [перша] не існує:
      1. Ми повертаємось false as перший має з’явитися пізніше в масиві
    3. If позиція [друга] не існує:
      1. Повертати правда
    4. Повертати позиція [перша] <позиція [друга]
  4. Роздрукуйте результат

Впровадження рішення відносного масиву сортування Leetcode

Програма С ++

#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

Програма С ++

#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).