Пересекающийся список записей

Question

У меня есть 2 списка -

• List<String> RecordIdByPriority и
• List<String> RecordId.

Как следует из названия - первый список содержит записив порядке вставки приоритета.
Идея состоит в том, чтобы найти наличие записи с наивысшим приоритетом из второго списка.

Если список приоритетов содержит <A,D,E>, а второй содержит <B,E,M> - ожидаемый результат равен 'E'.

Учитывая, что второй список потенциально большой - какова структура данных / процедура для достижения этого наиболее эффективным способом

Answer 1

Вы можете выполнить некоторую однократную предварительную обработку, которая преобразует List<String> RecordIdByPriority в HashMap<String, Integer>, который сопоставляет каждый элемент списка с его положением в списке.В вашем примере {A -> 0, D -> 1, E -> 2}.Затем выполните один проход по списку RecordId, чтобы найти минимальный элемент в соответствии с хэш-картой.Элементы, не найденные на карте, имеют неявный приоритет + бесконечность.

Это означает, что вы можете найти элемент в O (n), где n - длина списка идентификаторов записей.

Answer 2

Я думаю, что классический цикл все еще должен быть эффективным для этого.

public String getHighestPriorityRecord(List<String> recordIdByPriority, List<String> recordId) {
    for (String record : recordIdByPriority) {
        if (recordId.contains(record)) {
            return record;
        }
    }

    // Not found
    return null;
}

• Лучшее: O(1)
• Среднее: O(n log n)?
• Худшее: O(n^2)

Если вы хотите ускорить его, вы можете превратить recordId в HashSet (создав новый экземпляр HashSet), так что contains() будет O(1), что фактически превратит наихудший случай этого алгоритма в O(n).