Цитата:
Сообщение от undefined
это сложность порядка O(N^2) получается.Интересно есть ли более оптимальные решения?
|
Почему же ? мы линейно ходим по массиву влево и вправо по вектору, выключая и включая свет по одному разу за проход. сложность - n*2
Можем хранить ссылку на последний левый и правый вагоны после каждого прохода.