Найти элемент в коллекции, который может стать актуальным после того, как будет найден другой элемент

Question

У меня возникли проблемы с эффективным алгоритмом для следующей проблемы, и мне было интересно, может ли кто-нибудь здесь помочь мне вне. И нет, это не домашнее задание. Любая помощь приветствуется!

Скажем, у меня есть коллекция со следующими элементами: {A, B, C, D, .... Z}.

Каждый элемент имеет определенные требования к блокировке, которые могут быть выполнены, и выполнение этих требований может разблокировать другие элементы в коллекции.

Изначально, пробирая коллекцию, элемент A заблокирован, но последующие итерации в коллекции приводят меня к элементу D, а после обработки элемента D я получаю необходимые компоненты, чтобы иметь возможность использовать элемент A. Аналогичным образом, элемент L первоначально заблокирован, но после обработки элемента O элемент L может быть обработан.

Помимо циклирования в два раза или в обратном порядке по коллекции и сортировки коллекции, существует ли другой способ обработки всех элементов в одном цикле?

Answer 1

Ну, если вы знаете, какие элементы могут быть разблокированы при доступе к элементу, вы можете посетить их в следующий раз - поскольку они с большей вероятностью будут разблокированы - вы всегда должны указывать указатель на место, к которому достигли начальный линейный поиск - и, возможно, счетчик, чтобы увидеть, прошли ли вы все элементы - так, что вы можете вернуться отсюда, если ваш визит в другой элемент не будет плодотворным. Это обычно не уменьшает Большой O, но может улучшить среднее время. Это предполагает, что вы можете выполнить поиск в течение O (1). Else Мне нравится идея перемещения заблокированных элементов в конец - или даже лучшее удаление разблокированных элементов (так как это добавит максимум n перемещаемых элементов времени) - это сэкономит некоторое время на перемещении массива/списка/SearchTree