kot:
FIFO буфер для поиска пар носков!!!!!!!!! ТОЧНО!!!!!!!
они же отсортируются там в конце концов!!!
найти пару носком можно будет максимум за один проход по буферу
О(n) от размерности носков!!!
dimaaan:
))))))))))))
dimaaan:
неповеришь, но я так делал. в результате понял следующее: ключевая характеристика - время доступа к одному носкку. у меня полка в шкафу узкая и тонкая, поэтому даже один проход занимал много времени. Решение очевидно! надо составить словарь. В качестве ключа и значения выступает любой из носков. Здесь встает необходимость в новой структуре данных: параКлючЗначение. Это организовавыется очень просто: носок, выступающий в роли Значения заворачивается в носок Ключ после стирки (инициализации). Положим, что носки без пары имеют нолевое значение.Таким образом получаем быстрый доступ к обоим носкам, сокращая перебор до тех пор, пока не найдем носок ключ с не нулевым значением
kot:
старый но проверенный метод!!
dimaaan:
при добавлении носков проверяем, если есть подходящий носок-ключ с нолевым значением, добавляем к нему второй носок