“in-place”是什么意思？

Question

翻转字符串中的单词（单词之间由一个或多个空格分隔）。现在要在原地完成。

什么是“在原地”？

- NibblyPig

---

看看这个帖子，了解在C/C++中如何实现这个功能的技巧：https://dev59.com/gXVC5IYBdhLWcg3wvT1a - Mia Clarke

@Banang：虽然这是回答一个不同的问题（反转一个字符串，而不是字符串中的单词，例如“dog bites man”变成“man bites dog”，而不是“nam setib god”）。 - Simon Nickerson

可能可以在https://dev59.com/wGQn5IYBdhLWcg3wxZcn找到答案。 - Yuan Wen

Answer 1

原地修改指的是您应该更新原始字符串，而不是创建一个新字符串。

取决于您正在使用的语言/框架，这可能是不可能的。（例如，在.NET和Java中，字符串是不可变的，因此如果不采用某些恶意黑客技巧，则无法对字符串进行原地修改。）

- LukeH

---

针对.NET或Java，这个问题可以重新表述为讨论一个字符数组或StringBuilder。 - Simon Nickerson

Answer 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

不幸的是，这需要额外的O(n)空间来创建数组b，而且分配通常是一个缓慢的操作。如果我们不再需要a，我们可以使用这个原地算法用它自己的翻转覆盖它：

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

有时候要进行原地操作非常困难，一个经典的例子是一般的非方阵矩阵转置。

另请参阅

• 原地算法
• 原地矩阵转置

- polygenelubricants

---

非方阵转置是否可以原地进行？毕竟它需要每一侧的不同维度。 一个2x3的数组变成一个3x2的数组？ - penguat

@penguat：矩阵将存储在一个6个元素的一维数组中。转置从行主序变为列主序，反之亦然，例如ABCDEF变为ADBECF。 - polygenelubricants

啊，是的，我现在明白了就地转置可能会很棘手，并且需要在实施之前进行大量的思考。 - penguat

Answer 3

您需要将原始字符串的内容反转，而不使用临时存储变量来保存字符串。

- Charles

---

这不是不可能吗？你至少需要一个循环计数器或指针，可能还需要两个。 - Simon Nickerson

好的，我的意思是一个存储变量来保存临时值。根据编程语言，你确实需要一个计数器或指针。 - Charles

Charles 指的是暂存储器，它保存的是“字符串”，而不是计数器或指针。@SimonNickerson - Yuan Wen