Задача: 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:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> countMap;
        vector<int> remaining;
        vector<int> result;

        for (int value : arr2) {
            countMap[value] = 0;
        }

        for (int value : arr1) {
            if (countMap.count(value)) {
                countMap[value]++;
            } else {
                remaining.push_back(value);
            }
        }

        sort(remaining.begin(), remaining.end());

        for (int value : arr2) {
            for (int i = 0; i < countMap[value]; i++) {
                result.push_back(value);
            }
        }

        result.insert(result.end(), remaining.begin(), remaining.end());
        return result;
    }
};

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