Условие

Даны два массива arr1 и arr2, элементы arr2 различны, и все элементы arr2 есть в arr1.

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

Примеры

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]

Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6] Output: [22,28,8,6,17,44]

Решение

fun relativeSortArray(arr1: IntArray, arr2: IntArray): IntArray {
    val count = IntArray(1001) // подсчёт частоты встречаемости элементов arr1
    for (num in arr1) {
        count[num]++
    }

    val result = IntArray(arr1.size)
    var idx = 0

    // добавляем элементы в порядке, заданном arr2
    for (num in arr2) {
        repeat(count[num]) {
            result[idx++] = num
        }
        count[num] = 0
    }

    // оставшиеся элементы добавляем в порядке возрастания
    for (num in count.indices) {
        repeat(count[num]) {
            result[idx++] = num
        }
    }

    return result
}

Временная сложность

O(n + m), где n — размер arr1, m — размер arr2.

Пространственная сложность

O(n), для хранения результирующего массива и подсчёта элементов.