Алгоритм предложения - поиск по списку номеров

Question

У меня есть 7-значный список номеров. И я должен выполнить операцию поиска в списке. Ввод программы будет таким, как этот 5xx9xx1. Минимум 3 цифры будут известны. И индекс известных цифр не важен. Какой алгоритм вы бы предложили? Я не хочу искать в базе данных с запросом «как».

Answer 1

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

Вы также разделяете списки и выполняете поиск параллельно, если это оказывается слишком медленным.

Answer 2

Я предполагаю, что список исходных номеров, который у вас отсортирован. Если он не отсортирован, вам лучше его сортировать, поскольку с отсортированным списком вы можете получить числа с довольно прямым алгоритмом. Однако, если это не критическая операция времени, вам лучше использовать хеш-таблицу или структуру данных B-Tree. B-Tree может предоставить вам время запроса журнала (n). Это проще реализовать.

С отсортированного списка, вы можете перейти к соответствующим элементам непосредственно, если вход определяет позиции и значение поиска, то есть, если вход говорит смотреть только на цифры, которые имеют 5, 9 и 1 в положениях 6, 3 и 0 соответственно, вы можете напрямую перейти непосредственно к индексу 5,000,000, и вам не нужно искать значения за пределами 5,999,999.

Ключ понимание заключается в том, что если вы ищите номер (I) в положении X, и вы нашли первое такое количество N в этом положении, затем следующие последовательные 10^X-1 чисел будут иметь I в том же положении , Следующий набор номеров, который будет иметь I, равен X, будет иметь индекс N + 10^(X+1).

Например, если вы ищете для чисел с 5 в положении 2, и если вы на скажем 10000500, то вы можете прочитать следующие 10^2-1(99) номера в чем-то, что будет соответствовать этому условию. Следующий набор находится в позиции 10000500 + 10^3 = 100001500.

В вашей проблеме, хотя у вас есть несколько таких условий, так что вы начинаете с номера в самом высоком положении, а затем идите дальше в более мелкие позиции и переходите к наборам чисел. Если следующий набор, на который вы переходите, больше, чем диапазон, допустимый номером в самом верхнем положении, вы переходите к значению, указанному номером в более высоком положении.

Например, если вы ищете число с 5 в положении 2 и 3 в положении 1, вы начинаете 10000530. Следующие номера 10^1 будут соответствовать вашему критерию. Следующий комплект для 3 будет равен 10000530 + 10^2 = 10000630, но это превышает предел, установленный на 5 в позиции 2, что составляет 99. Таким образом, вы переходите к следующему набору, указанному 5, что составляет 10001530.

Этот метод является линейным по времени, w.r.to для выходного набора, так что вы можете иметь огромный вход, и если ваш выход действительно мал, метод выйдет очень быстро. Если вы используете B-Tree или какой-то такой метод, они будут зависеть от размера ввода.