Задача: 1122. Relative Sort Array
Сложность: easy

Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1.

Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания.

Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

👨‍💻 Алгоритм:

1⃣Инициализация и подсчёт:
Инициализируйте пустой массив result и массив remaining для хранения оставшихся элементов.
Создайте хеш-таблицу countMap для хранения количества вхождений каждого элемента из arr2 в arr1.

2⃣Заполнение countMap и remaining:
Пройдитесь по элементам arr1 и если элемент присутствует в countMap, увеличьте его счетчик. Если элемент не присутствует в arr2, добавьте его в remaining.

3⃣Формирование результирующего массива:
Пройдитесь по arr2 и добавьте элементы в result в соответствии с их количеством в countMap.
Отсортируйте массив remaining и добавьте его элементы в result.
Верните result в виде массива.

😎 Решение:

class Solution {

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> countMap = new HashMap<>();
        List<Integer> remaining = new ArrayList<>();
        List<Integer> result = new ArrayList<>();

        for (int value : arr2) {
            countMap.put(value, 0);
        }

        for (int value : arr1) {
            if (countMap.containsKey(value)) {
                countMap.put(value, countMap.get(value) + 1);
            } else {
                remaining.add(value);
            }
        }

        Collections.sort(remaining);

        for (int value : arr2) {
            for (int j = 0; j < countMap.get(value); j++) {
                result.add(value);
            }
        }

        result.addAll(remaining);

        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

Ставь 👍 и забирай 📚 Базу знаний