p
Чего ловко? Человек с соседнего чата спросил, я перепостил
Size: a a a
2021 February 10
p
Пометка: вопрос не мой
DM
Сложность
О(n*m) не смущает?p
Я попозже влезу, думаю по сложности довести до квадратной или даже логарифмической, но по памяти просесть
DM
Дык квадратная это и будет n*m
DM
Я думаю эффективно тут решить так:
слить оба массива
сортануть их, сохраняя признак (к А или Б относится элемент), а потом пройтись по нему вывести результат
слить оба массива
сортануть их, сохраняя признак (к А или Б относится элемент), а потом пройтись по нему вывести результат
DM
будет логарифмическая сложность
p
Я думаю эффективно тут решить так:
слить оба массива
сортануть их, сохраняя признак (к А или Б относится элемент), а потом пройтись по нему вывести результат
слить оба массива
сортануть их, сохраняя признак (к А или Б относится элемент), а потом пройтись по нему вывести результат
Собсно так я и сделал, способ в лоб. Скорость не мерил
DM
Почему в лоб?
DM
В лоб было бы ходить по массиву А и для каждого элемента ходить по массиву Б в поисках соседей. Тут была бы квадратичная сложность
j
EGD
зачем оба массива сливать?
зачем оба массива сливать?
DM
А сортировка быстрее отработает
DM
А как ты соседей искать будешь, если не сливать?
DM
Сортануть B и потом идти по A и бинарным поиском искать ему соседей?
j
EGD
сортируешь Б и ищешь в цикле по каждому А ищешь первый меньший A[i] в Б
сортируешь Б и ищешь в цикле по каждому А ищешь первый меньший A[i] в Б
DM
Дык как искать?
DM
Бинарно?
DM
logn такой поиск
DM
сортировка тоже logn
DM
logn^2 получишь