Эффективный метод нахождения лексического минимума диапазона целых чисел

#algorithm #sorting #minimize

#алгоритм #сортировка #минимизировать

Вопрос:

Учитывая два положительных целых числа, скажем, M и N, с M < N, какой наиболее эффективный алгоритм для нахождения минимума в лексикографическом порядке строк целых чисел от M до N, представленных в десятибазионном ASCII без начальных нулей? Например, для [200, 10890] ответ равен ‘1000’, для [298, 900] ответ равен ‘298’.

Ответ №1:

введите описание изображения здесь

1. Это выражение сначала завершается ошибкой при M = 1, N = 10. Я думаю, что вторая строка должна быть «return 10 ^(ceil(log_10(M))». В противном случае это не сработает, если M равно степени 10. Тогда первая строка должна быть: «если ceil(log_10(M)) <= floor(log_10(N))».

2. Теперь записанное выражение таково: если ceil(log_10(M)) <= log_10 (N), то верните 10 ^ (ceil(log_10(M))), иначе верните M end if (на случай, если imgur когда-либо удалит это изображение …)

Ответ №2:

Я думаю, вы, вероятно, правы в своей интуиции, что для этого существует алгоритм с постоянным временем. Сначала вы должны найти наименьшую первую цифру, затем наименьшую вторую цифру и т.д.

1. Если быть немного педантичным, это линейное время (по количеству цифр во входных данных).

2. Да, вы абсолютно правы — он линейный по количеству цифр, что, я полагаю, технически делает его логарифмическим для N.