Заменить 2 цифры в числе так, чтобы оно стало наибольшим за O(n)

#cpp #python #алгоритм #строки #числа

  Дано число, в записи которого может присутствовать до 10^5 цифр. В
  этом числе можно поменять любые две цифры местами. Среди всех этих
  замен нужно найти ту, при которой получается наибольшее число.


За O(n²) решается легко. Как решить за O(n) или за O(n⋅log(n))?

Примеры:

1234 => 4231
9997754321 => 9997754321

    

Ответы

Ответ 1

Запишем цифры первоначального числа в массив a. (Если цифр у числа много, то скорее
всего число вам уже дано именно в таком виде.) Скопируем массив в массив b и отсортируем
его в порядке убывания.

Найдём первый индекс такой, что a[i] != b[i]. Если такого индекса нет, перестановка
не нужна, порядок оптимальный. Пусть это индекс k. Очевидно, b[k] >= a[i] для i >=
k, причём b[k] != a[k] по выбору k. Значит, b[k] — максимальное из оставшихся чисел.

Очевидно, b[k], b[k+1], ... — перестановка чисел a[k], a[k+1], ..., поэтому b[k]
== a[l] для некоторого l > k. (l != k, т. к. b[k] != a[k]). Возьмём наибольшее такое l.

Перестановка индексов k и l — искомая.



Сложность: O(n log n) { сортировка } + O(n) { поиск k } + O(n) { поиск l } = O(n log n).



Обновление: Поскольку мы сортируем цифры, то сложность сортировки можно уменьшить
до O(n), применив сортировку подсчётом. Итоговая сложность O(n).



Примечание: Можно избавится от дополнительного массива b, если заменить его просто
на количество 9-ок, 8-ок, 7-ок и т. д. (эта информация используется в сортировке подсчётом),
за счёт некоторого усложнения кода. Таким образом мы получаем всего лишь O(1) дополнительной
памяти.


Ответ 2

Вот реализация на Питоне линейного (O(n)) алгоритма c постоянной дополнительной памятью
(O(1)), описанного в ответе @VladD:



#!/usr/bin/env python3
from collections import Counter

def make_largest_by_swapping_2_digits(digits):
    """O(n) time, O(m) space"""
    # find where given number differs from the largest number with the same digits
    multiplicity = Counter(digits) # count how many times each digit occurs
    all_digits = sorted(multiplicity, reverse=True) # m digits in decreasing order
    largest = (d for d in all_digits for _ in range(multiplicity[d]))
    for k, (a, b) in enumerate(zip(digits, largest)):
        if a != b:
            break
    else: # already largest possible
        return # nothing to swap

    # find on the right where a == b
    j = next(len(digits) - i for i, a in enumerate(reversed(digits), 1) if a == b)
    digits[k], digits[j] = digits[j], digits[k] # swap


Пример:

digits = [1,2,3,4]
print('before', *digits)
make_largest_by_swapping_2_digits(digits)
print('after ', *digits)


Результат

before 1 2 3 4
after  4 2 3 1


Заметки по коду:


Counter() просто считает сколько раз каждая цифра встречается:

print(Counter(str(9997754321)))
# -> Counter({'9': 3, '7': 2, '5': 1, '4': 1, '3': 1, '2': 1, '1': 1})


Потребление памяти O(m), где m не более 10 для десятичной системы. Можно считать
константой.

Counter по сути multiset здесь (набор цифр с повторениями). Если ограничить тип цифр
только целыми десятичными, то можно простой массив использовать вместо Counter:

multiplicity = [0] * 10
for d in digits:
    multiplicity[d] += 1

largest это наибольшее число, составленное из тех же цифр что и входное число. Для
представления используется генератор, поэтому дополнительная память нужна только для
одной цифры в каждый момент O(1)
enumerate(zip()) позволяет обойти две последовательности одновременно по одной паре
элементов за раз, отслеживая текущий индекс:

>>> list(enumerate(zip(range(3), "abc")))
[(0, (0, 'a')), (1, (1, 'b')), (2, (2, 'c'))]

make_largest_by_swapping_2_digits(digits) принимает любую изменяемую последовательность
(list, bytearray, mmap, etc) c хэшируемыми элементами, которые можно сравнивать.


Например, для больших чисел, записанных в файле, можно с mmap напрямую работать (предполагая,
что отдельная цифра в байте помещается):

import mmap

with open('много-цифр.txt', 'r+b', 0) as file, \
     mmap.mmap(file.fileno(), 0, access=mmap.ACCESS_WRITE) as digits:
    make_largest_by_swapping_2_digits(digits)


После выполнения кода, файл много-цифр.txt будет содержать новое число—изменение
по месту происходит.