arrays - 重新排列旋转的排序数组

Question

我见过几个与旋转排序数组相关的问题，例如搜索枢轴元素或搜索此类数组中的元素。

但是，我没有发现任何与在不使用排序的情况下将此类数组重新排列为其原始形式有关的问题。

所以我的问题是：*有没有一种有效的方法或技巧，可以在不使用额外内存的情况下将旋转的排序数组重新排列为原始形式？

Answer 1

这是我要做的事情。我会使用二进制搜索的变体找到起始元素。

一旦找到，如果你可以使用外部存储器，它可以在 O(n) 中完成所以总时间是 O(lgn) + O(n) 即 O(n)

具体到轮换：看到 ajay 的评论，我同意既然我们必须就地轮换，最好的选择是冒泡排序。这是 O(n*m) 其中 m 是旋转的元素数。

但是，如果我们可以使用一些存储来保存起始元素两侧的元素，基本上，如果我们可以使用外部存储器，那么只需将每个元素放在新数组中的正确位置即可。