Д
Paul
ребят, кто знает, какое каноничное решение у задачи про слияние двух сортированных массивов?
(a+b).sort нельзя, если что :)
Size: a a a
2020 July 09
R
бидон в чате
R
Paul
ребят, кто знает, какое каноничное решение у задачи про слияние двух сортированных массивов?
(a+b).sort нельзя, если что :)решение простое - два указателя
R
на два начала - на один и на другой массив
R
ну и цикл пока до конца не дойдет
R
т.к. массивы отсортированы уже, то надо делать проверку какой элемент меньше и его вставлять
R
потом идешь постепенно, сравниваешь с тем, что есть
R
сложность получается линейная O(N) - т.е. самая лучшая (в этом случае)
R
под указателем я имею в виду индекс элемента просто - типа
i для первого и j для второгоR
типа того:
arr1 = [1, 4, 10, 20, 100]
arr2 = [2, 3, 9, 25, 99, 200, 300, 400]
arr = []
i = 0
j = 0
loop do
if arr1[i] && arr1[i] < arr2[j]
arr << arr1[i]
i += 1
elsif arr2[j]
arr << arr2[j]
j += 1
else
break
end
end
puts arr.inspect
R
вывод:
[1, 2, 3, 4, 9, 10, 20, 25, 99, 100, 200, 300, 400]
R
(наверное не всегда работает, немного надо потестить - но принцип похожий)
Д
типа того:
arr1 = [1, 4, 10, 20, 100]
arr2 = [2, 3, 9, 25, 99, 200, 300, 400]
arr = []
i = 0
j = 0
loop do
if arr1[i] && arr1[i] < arr2[j]
arr << arr1[i]
i += 1
elsif arr2[j]
arr << arr2[j]
j += 1
else
break
end
end
puts arr.inspect
А если имена массивов поменять местами? :)
R
ну вот допиши - покажи класс)
P
Мой сын утверждает, что птицы - это выжившие динозавры)
он в принципе прав. 160 млн лет назад они отделились от динозавров
PT
птицы - это динозавры, которые активнее других махали лапами, когда падали с деревьев
P
А если имена массивов поменять местами? :)
вот это важный момент, они могут быть разной длины, что первый, что второй
P
во время интервью меня наводили на факт, что оба массива отсортированы
P
это можно использовать для бинарного поиска
P
не совсем понятно, что и где искать