根据杜克林的评论，我意识到我提出的解决方案实际上不是线性的，而是线性的，甚至更糟——你无法控制它是否需要额外的内存。在我的第二个想法中，我意识到你对数组了解很多，你可以实现一个更具体但可能更容易的解决方案。

我将假设数组中的所有值都是正值。我需要这个，这样我就可以使用负值作为“已处理”的标志。我的想法是以下-从左到右迭代数组。对于每个元素，如果它已经被处理（即它的值是负值），只需继续下一个。否则，您将有一个常量公式，其中是该元素应该在的位置：

• 如果值是奇数并且它的索引是i它应该移动到i*2
• 如果值是偶数并且它的索引是i它应该移动到（i-n/2）*2 1

将此值存储到临时值中，并使数组当前索引处的值为0。现在，直到我们“手头有”的值不为零的位置，将其与停留在我们应该根据上述公式放置它的位置的值交换。此外，当您将手头的值置为负时，将其“标记为已处理”。现在我们有了一个新值“手头有”，我们再次根据上述公式计算它应该去哪里。我们继续移动值，直到我们“手头有”的值应该去0的位置。稍微思考一下，你就可以证明你手头永远不会有一个负的（“处理过的”）值，最终你会在数组的空白处结束。

处理完所有值后，在数组上迭代一次以否定所有值，您将获得所需的数组。我描述的算法的复杂性是线性的——每个值将不超过一次“在手边”，您将不超过一次迭代它。