Помогите ускорить реализацию F задачи яндекса на Swift

Question

Всем привет. Недавно открыл для себя IOS разработку, swift и прочие радости. Начитался книжек, насмотрелся ютуба и в итоге нашел задачи яндекс.интервью. С последней, F задачей никак не получается справиться, сначала уперся в память, поменял типы данных с Int на UInt8 для хранения массива, теперь уперся во время выполнения.

Логика примитивная, с readline() заполняется массив UInt8, потом array.sort(), потом вывод массива через print() (C файлами работать пока не умею).

Если кто решал эту задачку на swift - подсобите советом как ее ускорить?

ЗЫ TL случается на 20-м тесте

текст задачи: F. Слияние k сортированных списков Даны k отсортированных в порядке неубывания массивов неотрицательных целых чисел, каждое из которых не превосходит 100. Требуется построить результат их слияния: отсортированный в порядке неубывания массив, содержащий все элементы исходных k массивов.

Длина каждого массива не превосходит 10⋅k.

Постарайтесь, чтобы решение работало за время k⋅log(k)⋅n, если считать, что входные массивы имеют длину n.

Формат ввода Первая строка входного файла содержит единственное число k, k ≤ 1024.

Каждая из следующих k строк описывает по одному массиву. Первое число каждой строки равняется длине соответствующего массива, оставшиеся числа этой строки описывают значения элементов этого же массива. Элементы массивов являются неотрицательными целыми числами и не превосходят 100.

Формат вывода Выходной файл должен содержать отсортированный в порядке неубывания массив, содержащий все элементы исходных массивов.

Пример

Ввод    
4
6 2 26 64 88 96 96
4 8 20 65 86
7 1 4 16 42 58 61 69
1 84

Вывод
1 2 4 8 16 20 26 42
58 61 64 65 69 84 86
88 96 96

код:

let arrCount = Int16(readLine() ?? "") ?? -1
var resultArr:[UInt8] = []
for _ in 1...arrCount {
    var i = 0
    let readArr = Array(readLine() ?? "")
    var num = ""
    while readArr[i] != " " {
        num += String(readArr[i])
        if i < readArr.count - 1 { i += 1 } else { break }
    }
    if i < readArr.count - 1 { i += 1 } else { break }
    var numsCountInLine = Int16(num) ?? -1
    while numsCountInLine > 0 {
        num = ""
        while readArr[i] != " " {
            num += String(readArr[i])
            if i < readArr.count - 1 { i += 1 } else { break }
            if i == readArr.count { break }
        }
        resultArr.append(UInt8(num) ?? 0)
        if i < readArr.count - 1 { i += 1 }
        numsCountInLine -= 1
    }
}
resultArr.sort()
if resultArr.count > 0 {
    for i in 0...resultArr.count-1  {
        print(resultArr[i])
    }
}

Answer 1

время k⋅log(k)⋅n говорит о том, что авторы могли иметь в виду многопутевое слияние. При этом заводится очередь по приоритетам из k элементов на основе бинарной кучи (min-heap), в которую складываются пары (текущее значение или текущий индекс i-го списка; номер списка i). На каждом шаге снимается элемент с вершины очереди, его значение идёт в выходной массив, а номер списка используется, чтобы вставить в очередь следующий элемент из того же списка.

Кроме того, очень сильное ограничение неотрицательных целых чисел, каждое из которых не превосходит 100 позволяет использовать эффективную сортировку подсчётом - просто завести массив целых из 100 элементов и посчитать количество каждого из дозволенных чисел, а в конце заполнить выходной массив соответствующим количеством копий

Answer 2

Как правильно подсказал Mbo тут дело в сортировке подсчетом, но как выяснилось этого недостаточно, чтобы ручной парсинг строки с числами успевал отрабатывать. Поэтому с наставлениями старших товарищей верный код для решения выглядит так:

var resultArr = Array(repeating: UInt32(0), count: 101)
let arrCount = Int16(readLine() ?? "") ?? -1
if arrCount != -1 {
    for _ in 1...arrCount {
        let line = readLine()!
        let nums = line.split(separator: " ").dropFirst()
        nums.forEach {
            let index = Int($0)!
            resultArr[index] += 1
        }
    }

    for i in 0...100  {
        if resultArr[i] > 0 {
            for _ in 1...resultArr[i] {
                print(i)
            }
        }
    }
}

БЛОГ НА HUSL

Помогите ускорить реализацию F задачи яндекса на Swift

Ответы (2 шт):