Как я выбираю все элементы в списке, которые неисправны?
Так как типы содержатся в домене приложения, я ожидал бы, что статические классы будут присутствовать, пока домен приложения не переработан, или если запрос подается различным доменом приложения.
я могу думать о нескольких способах сделать объекты характерными для конкретного запроса, зависит от того, что Вы хотите сделать, для, например, Вы могли инстанцировать объекта в Приложении. BeginRequest и затем хранят его в объекте HttpRequest так, чтобы к этому могли получить доступ все объекты в конвейере обработки запросов.
3 ответа
Вероятно, лучший подход к этому - сначала найти самую длинную возрастающую подпоследовательность , а затем считать, что все элементы, не являющиеся частью этой последовательности, вышли из строя. Алгоритм, представленный на связанной странице, выполняется за O (n log n) времени и использует O (n) пространство (в дополнение к пространству самого списка).
Такое такой подход определенно даст правильный ответ для вашего примера, поскольку самой длинной возрастающей подпоследовательностью будет последовательность от 1 до 11, не включая лишние 5 и 10.
Как алгоритм должен знать, какие элементы вы считаете неисправными?
Если действует правило «список [i + 1] всегда должен быть списком [i] + 1», то, конечно, будет легко запомнить, что после 1 следующим элементом должно быть 2, выберите те, что в между и так далее. Но вам нужно точное правило, чтобы алгоритм определял, какие элементы следует считать "вышедшими из строя".
Как сказал Дэв, самая длинная возрастающая подпоследовательность , вероятно, лучшее, что вы можете сделать.
это не в моей голове, поэтому он может (читай, вероятно, нет: P) исправить: Очевидная нижняя граница для этой проблемы - O (n), поскольку вам нужно как минимум один раз прочитать каждое число. Но предположим, что существует алгоритм, работающий за O (n) раз. Затем вы можете просто вставить неупорядоченные элементы по порядку за линейное время, но лучший алгоритм сортировки сравнения имеет нижнюю границу O (nLogn), так что это противоречие. (в противном случае существуют методы сортировки без сравнения, такие как сегментная или поразрядная сортировка, которые либо используют много памяти, либо используют размер сортируемых чисел ...)