Решение Leetcode для массива относительной сортировки  


Сложный уровень Легко
Часто спрашивают в саман Амазонка Де Шоу eBay Google Microsoft
алгоритмы массив кодирование HashMap Интервью подготовка к собеседованию LeetCode LeetCodeSolutions Сортировка

В этой задаче нам даны два массивы натуральных чисел. Все элементы второго массива различны и присутствуют в первом массиве. Однако первый массив может содержать повторяющиеся элементы или элементы, которых нет во втором массиве.

Нам нужно отсортировать первый массив и вернуть его, сохраняя относительный порядок его элементов таким же, как и во втором массиве. Элементы, которых нет во втором массиве, должны появляться в конце массива неубывающим образом. Элементы в массиве не будут превышать значение 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. , в противном случае.

Алгоритм

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

Реализация решения 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

Анализ сложности решения Leetcode для массива относительной сортировки

Сложность времени

O (макс (NlogN, M)) в котором N = размер первого массива и M = размер второго массива. Мы выполняем один проход для второго массива, который занимает O (M) времени, и сортируем первый массив, который занимает O (NlogN) времени, предполагая, что сравнение выполняется за постоянное время.

Смотрите также
Проверьте, является ли это решение Leetcode для прямой линии

Космическая сложность

О (М) поскольку мы храним индексы элементов второго массива в хэш-карте.

Подход (счетная сортировка)  

Предположим, что Array1 = {1, 2, 2, 2} и Array2 = {2, 1}. Начните обход второго массива. Сначала мы видим целое число 2. Если бы мы знали, что существует 3 двойки, мы бы легко записали эти значения в массив Array2, начиная с индекса 1. Тогда у нас есть целое число 0 в массиве Array1. Опять же, если бы мы знали его частоту, мы бы легко сохранили их после двоек. Аналогичным образом мы можем сохранить частоты всех элементов в Array2, а затем запустить один проход Array1, перезаписав элементы в Array2 в соответствии с их частотами.

Но даже после этого мы бы игнорировали те элементы, которые присутствуют в 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 для массива относительной сортировки

Программа 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], чтобы заполнить любой левый элемент.

Смотрите также
Количество шагов по сокращению числа до решения с нулевым кодом Leetcode

Космическая сложность

O (1) поскольку мы используем постоянное пространство, которое в этом случае равно O (1000), чтобы хранить частоту элементов.