как найти индекс элемента в структуре данных ArrayDegue?
Как очень быстро найти индекс элемента в ArrayDegue? Есть задача где по заданному числу нужно определить его индекс, не проходит один тест, ограничение по времени. Пробовал индексофф, не сработало
Ответы (1 шт):
Если исходная коллекция значений отсортирована, нужно использовать двоичный поиск, сложность составит O(log N).
Для неотсортированной коллекции в общем случае придётся проитерировать по ней хотя бы один раз, то есть сложность поиска будет линейной O(N).
Однако, если будет выполняться многократный поиск по одной и той же коллекции, его можно ускорить, построив карту (мапу) индексов, то есть исходная коллекция Collection<T> преобразуется в мапу Map<T, Integer>, если все значения уникальны или если нужно запоминать только один (первый) индекс, или же Map<T, List<Integer>> -- чтобы для каждого значения хранить отсортированный список всех индексов. Поскольку "стоимость" поиска по ключу в мапе принимается равной константе O(1), при повторных попытках индекс будет находиться гораздо быстрее.
При этом у типа значений T должны быть корректно реализованы методы equals и hashCode, так как они будут использоваться в качестве ключей.