Алгоритм для поиска наименьшего целого числа путем замены пары цифр в заданном целое число

Ответ 1

В качестве подготовки мы прокручиваем цифры и отмечаем последние позиции цифр в массиве [10] (назовем его last) (включая 0 s). Это O (n).

Затем мы начинаем перебирать цифры слева направо. Для каждой позиции мы пытаемся найти наименьшую цифру, последняя позиция которой больше нашей текущей позиции (ограничение позиции). Также эта цифра должна быть меньше текущей цифры.

Если мы находимся в первой позиции, мы начинаем цикл на last из 1 (иначе от 0), до значения текущей цифры (не включая).

Если мы найдем такую ​​цифру (относительно ограничения позиции), мы поменяем (и сломаем цикл). Если мы этого не сделаем, мы перейдем к следующей цифре. Стоимость не более O (n * 9), которая равна O (n).

Общая стоимость O (n) + O (n) * O (9) = O (n).

Как работает алгоритм на примерах:

93561 ->   it can swap in the first cycle

596   ->   skipping the first cycle, 
           then finds '6' because of the position constraint 
           (comparing position '1' with last[5] = 0, last[6] = 2)

10234 ->   does not find anything because of the position constraint

93218910471211292416 -> finds the last occurrence of '1' to replace '9'

98761111 -> it can swap in the first cycle
            (last[1] = 7, so it will change the last occurrence)

555555555555555555596 -> iterates until the '9', then you skip last[5]
            but finds last[6] as a good swap

120 ->      at pos 0 (1) cannot find a non-zero element less than 1, so skip
            at pos 1 (2) can find 0 on position 2, so we swap

Еще раз, здесь мы делаем одну итерацию по цифрам (для предварительного анализа данных), затем одну итерацию для поиска MSB. Во второй итерации мы повторяем на last, который является постоянным размером (не более 9).

Вы можете дополнительно оптимизировать алгоритм, добавив отслеживание минимального значения, когда стоит начать цикл на last, но это уже оптимизация. Версия prevoius содержала это, проверьте историю, если вам интересно:)

Ответ 2

Сначала подсчитайте каждую цифру, сохраните ее в массиве (counts[10]).

Пройдя слева, проверьте цифры (следующее описание цикла):

Проверьте, есть ли цифра в counts, которая меньше, чем она. Выберите самый маленький. Исключение: 0 не допускается для самой первой цифры.

• Если есть, поменяйте, вы закончите (выйдите из цикла!).
• В противном случае уменьшите цифру в counts и перейдите к следующей цифре.

Для каждой цифры вы выполняете O (1). Таким образом, весь алгоритм O (n).

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

Ответ 3

Я бы перебирал массив, начиная с правого конца. Сохраните цифру справа как наименьшую цифру и максимальную цифру и начните движение влево, если вы нажмете новое меньшее число, назовите его наименьшим. Если вы продолжаете двигаться влево, и вы найдете меньшее число, сделайте меньший потенциал. Если вы обнаружите большее число, сделайте потенциал меньшим наименьшим int и сохраните более крупный как максимальную цифру. Каждый раз, когда вы нажимаете большую цифру, чем ваш самый маленький, сделайте ее новой максимальной цифрой. Если вы попали в конец, замените максимальную цифру и наименьшую цифру. В python (Это работает и является O (n))

def swap_max(digits):
    i = len(digits) - 1
    while i > 0:
        if digits[i] == 0:
            i-= 1
        else:
            break
    max_i = i
    min_i = i
    pot_i = i
    z_i   = -1
    nz_i  = i
    i = len(digits) - 1
    while i >= 0:
        if digits[i] > digits[pot_i]:
            max_i = i
            min_i = pot_i
        if digits[i] < digits[min_i] and digits[i] != 0:
            pot_i = i
        if digits[i] == 0 and z_i == -1:
            z_i = i
        if digits[i] != 0 and i > 0:
            nz_i = i
        i -= 1
    if z_i != -1 and max_i != 0 and max_i < z_i:
        min_i = z_i
        i = nz_i
        max_i = i
    elif max_i == min_i and z_i != -1:
        i = nz_i
        if i < z_i:
            min_i = z_i
            max_i = i

    v = digits[min_i]
    digits[min_i] = digits[max_i]
    digits[max_i] = v
    return digits


#TESTING THE FUNCTION
tests =   [93561,596,10234,120,10091,98761111,1001,1010,1103,120,93218910471211292416]
results = [13569,569,10234,102,10019,18761119,1001,1001,1013,102,13218910471211292496]
tests = map(list,map(str,tests))
results = map(list,map(str,results))
for i in range(len(tests)):
    res ="".join(map(str,swap_max(map(int,tests[i]))))
    print res,"".join(results[i])
    if res=="".join(results[i]):
        print "PASSED\n"
    else:
        print "FAILED\n"

Это закончилось тем, что работало на всех примерах. Это также имеет преимущество использования памяти O (1).

Ответ 4

Вот простой алгоритм O(n):

- Record 'false' for each of ten digit values, 0 through 9
- Work through the number digits, left-to-right
    - If the digit value is associated with 'true' go to the next digit and continue
    - Record 'true' for this digit
    - Search all the digits to the right for the right-most, smallest digit
      (except zero for the first digit in the number)
      and swap if the lowest digit found (if any) is less than the current digit
    - If swapped, report success and stop
    - If not swapped, go to the next digit and continue
- If we reach the end of the digit list, report a lack of success and stop

Это может показаться не O (n) при первой проверке, однако, осознав, что внутренний цикл может выполняться не более десяти раз, становится очевидным, что это O(n) с O(n - 10 + 10*n) = O(11*n - 10) = O(n).

Ответ 5

PseudoCode: O (n)

1) Разделите число на отдельные цифры, например цифру [10] (как сказано в другом ответе). Init incPos = -1.

2) Пройдите справа от самой цифры, чтобы найти наибольшее значение по умолчанию (incPos). т.е. при перемещении сравнить k + 1 элемент с k-м элементом. Для каждой цифры [k] ≠ 0, If digit[k] >= digit[k+1] затем отметьте incPos как k. Поверните до самого левого и найдите наименьший incPos.

4) Если incPos == -1 возвращает num, else переходите форму incPos к n, чтобы найти цифру Right-Most-Minimum (как описано в БЛОКЕ ниже), своп с наименьшим минимальным значением цифры и возврата. (конечно, будет по крайней мере 1 цифра.)

E.g  
93561 ->                IncPos = 0,  Right most minimum : 1 at pos 4 
596   ->                IncPos = 1,  Right most minimum : 6 at pos 2 
10234 ->                IncPos = -1, return 10234  
93218910471211292416 -> IncPos = 0,  Right most minimum : 1 at pos 18 
98761111 ->             IncPos = 0,  Right most minimum : 1 at pos 7 

5) Введите число с новыми цифрами. Возвращаемый номер.

Ответ 6

Незначительное изменение алгоритма Каролова Хорвата

Вы можете преобразовать массив цифр в O (n).

Теперь у нас есть 2 списка: отсортировано и актуально. Фактически это наш оригинальный массив.

Итерации по фактическому слева направо,

для каждого значения, Выбросьте элементы из Sorted, пока мы не достигнем значения, положение которого в исходном массиве равно < положение фактического [i]

Если головка значения отсортированного списка равна < фактический [i], тогда мы поменяемся, и мы закончили. еще продолжить.

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

Конечно, существует специальная проверка случая для свопа 0 с самым левым элементом, но это не влияет на сложность.