假设我有以下数组:
1, 4, 5, 2, 3
我需要重新排列它
5, 1, 4, 2, 3
只有额外的空间;一个int
。
我想出了一个解决方案来解决它。但它是 O(n^2)
复杂度。
谁能提供更快的解决方案?
谢谢
编辑: 抱歉,不是旋转阵列。
我需要将原始数组更改为结果数组。 顺序可以是任意的。 我只需要制作 A -> B。 B 是有人告诉我的。
谢谢
已编辑 2"
让它更清晰。 数组 B 不固定。 我们需要为此找到一个通用的解决方案。
更新:
谢谢大家。看起来这是一个脑筋急转弯的问题。哈哈:D
Amazon 的面试官问了我的 friend 这个问题。哈哈
最佳答案
在我看来,这只是对数组进行排序的一种特殊情况,排序顺序相当随意。因此,最佳算法的时间复杂度为 O(n log n),而使用就地排序算法(以不稳定排序为代价)的空间复杂度为 O(1)。就地merge sort符合要求,就地 quicksort 也是如此如果平均 O(n log n) 没问题。
关于algorithm - 以比 O(n^2) 更快的时间重新排列具有 O(1) 额外内存的数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10002690/