0
Это было предложено мне в интервью,дизайн стек, который обеспечивает popMin() в постоянная время
меня впервые попросили разработать стек, который делает getMin() в постоянное время. Это довольно известная проблема, когда вы добавляете дополнительное поле в элемент стека и поддерживаете значение min. Затем меня попросили расширить эту функциональность, чтобы обеспечить постоянное время работы popMin(). Я рисую пробел о том, как это сделать. Есть идеи?
Другие операции, разрешенные занять больше времени, чем обычно (например, Θ (log n) 'push')? Если нет, это нарушит привязку Θ (n log n) для сортировки сортировки. – delnan
nope, все постоянное время. Я на самом деле предложил нарушить идею стека, используя связанный список для создания стека, сохранить указатели на минимальные узлы, а затем просто удалить их напрямую. Dunno, если они на самом деле чувствовали, что это нормально – Aks
Я имею в виду тот факт, что эта структура данных будет математически невозможна: она позволила бы линейный алгоритм сортировки времени, вставив все элементы в этот стек, а затем повторно 'popMin()' - ING. Это, как известно, невозможно, когда вы заказываете функцию сравнения черного ящика. Если значения были целыми, это может изменить ситуацию. Были ли вы предоставлены какие-либо другие ограничения или свободы? – delnan