Что означает "на месте"?

Ответ 1

На месте означает, что вы должны обновить исходную строку, а не создавать новую.

В зависимости от языка/рамки, которые вы используете, это невозможно. (Например, строки неизменяемы в .NET и Java, поэтому было бы невозможно выполнить обновление на месте на месте, не прибегая к каким-то злым хакам.)

Ответ 2

Внутрисегментные алгоритмы могут использовать только O(1) дополнительное пространство. Классический пример - разворот массива (по сути, вопрос интервью). Из Википедии взято следующее:

Предположим, мы хотим изменить массив из n элементов. Один простой способ сделать это:

function reverse(a[0..n])
    allocate b[0..n]
    for i from 0 to n
       b[n - i] = a[i]
    return b

К сожалению, для создания массива b для этого требуется O(n) дополнительное пространство, а распределение часто является медленной операцией. Если нам больше не понадобится a, мы можем вместо этого перезаписать его с помощью своего собственного обращения, используя этот алгоритм на месте:

function reverse-in-place(a[0..n])
    for i from 0 to floor(n/2)
       swap(a[i], a[n-i])

Иногда делать что-то на месте ОЧЕНЬ ЖЕСТКО. Классическим примером является общая неквадратная матричная транспозиция.

См. также

• На месте алгоритм
• Транзирование на месте матрицы

Ответ 3

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