algorithm - 以比 O(n^2) 更快的时间重新排列具有 O(1) 额外内存的数组

Question

假设我有以下数组:

1, 4, 5, 2, 3

我需要重新排列它

5, 1, 4, 2, 3

只有额外的空间；一个int。

我想出了一个解决方案来解决它。但它是 O(n^2) 复杂度。

谁能提供更快的解决方案？

谢谢

编辑:抱歉，不是旋转阵列。

我需要将原始数组更改为结果数组。顺序可以是任意的。我只需要制作 A -> B。B 是有人告诉我的。

谢谢

已编辑 2"

让它更清晰。数组 B 不固定。我们需要为此找到一个通用的解决方案。

更新:

谢谢大家。看起来这是一个脑筋急转弯的问题。哈哈:D

Amazon 的面试官问了我的 friend 这个问题。哈哈

Answer 1

在我看来，这只是对数组进行排序的一种特殊情况，排序顺序相当随意。因此，最佳算法的时间复杂度为 O(n log n)，而使用就地排序算法(以不稳定排序为代价)的空间复杂度为 O(1)。就地merge sort符合要求，就地 quicksort 也是如此如果平均 O(n log n) 没问题。