Я прохожу курс «Алгоритмы, часть I» на Coursera и застрял на бонусе на вопрос первого задания . Я уже представил свое решение и получил свои оценки. Это просто для любопытства.
Backwa sh - это отображение скрещенных участков как полное (синее) на этом изображении . Это происходит потому, что я использую виртуальные верхний и нижний узлы и соединяю строки под / над ними для удовлетворения требований сложности; Таким образом, соединение вершины с нижней частью приводит к тому, что все узлы, связанные с нижней частью, соединяются с верхней частью. Это описание может показаться неполным, поэтому я настоятельно рекомендую прочитать ссылку на спецификации.
Решение этой проблемы заключается в использовании другого объекта WeightedQuickUnion и дублировании в нем сетки, не включая нижний виртуальный узел. Теперь это решение не удовлетворяет требованиям памяти оценщика для бонусного вопроса (проверьте, что общая память <= 11 n ^ 2 + 128 n + 1024 байта). Я думал о некоторых обходных путях (например, использование массива / стека для хранения открытых сайтов в нижней строке), но все они используют дополнительный метод, имеющий сложность O (n), тогда как назначение не позволяет этого. Согласно спецификациям присваивания, кроме конструктора все методы должны иметь постоянное время + постоянное количество вызовов union () и find (). </p>