3

假设我有以下数组：

1, 4, 5, 2, 3

我需要重新安排它

5, 1, 4, 2, 3

只有额外的空间；一int。

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

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

谢谢

编辑：对不起，不是旋转阵列。

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

谢谢

编辑 2"

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

更新：

谢谢你们。似乎这是一个脑筋急转弯问题。哈哈 :D

我的朋友被亚马逊面试官问过这个问题。哈哈

4

4 回答 4

2

在我看来，这只是对数组进行排序的一种特殊情况，其中排序顺序相当随意。因此，最佳算法的时间复杂度为 O(n log n)，而使用进行就地排序的算法（以非稳定排序为代价）的空间复杂度为 O(1)。如果平均O(n log n) 是可以的，就地合并排序将符合要求，就地快速排序也将符合要求。

于 2012-04-03T23:21:54.287 回答
1

此解决方案使用 O(1) 空间工作。

>>> def arrayswap(source, dest):
...     for i in range(len(dest)):
...         source[source.index(dest[i])], source[i] = source[i], source[source.index(dest[i])]
... 
>>> a = [1, 4, 5, 2, 3]
>>> b = [5, 1, 4, 2, 3]
>>> arrayswap(a, b)
>>> a
[5, 1, 4, 2, 3]

如果不使用 python 的元组打包，source[i] 或 source[source.index(dest[i])] 之一的值可以存储在 int 中。

于 2012-04-03T23:48:51.180 回答
0

似乎您只是将前三个元素向左移动（环绕）。

所以，忽略索引 3 和 4。

  int temp = array[0]
  array[0] = array[1]
  array[1] = array[2]
  array[2] = temp
于 2012-04-03T23:21:54.023 回答
-1

你可以这样做：

temp = arr[0];
arr[0] = arr[2];
arr[2] = arr[4];
arr[4] = arr[1];
arr[1] = arr[3];
arr[3] = temp;

编辑：

要将数组 a 重新排列为数组 b，您可以这样做：

for (var i = 0; i < a.length; i++) {
  for (var j = i + 1; a[i] != b [i]; j++) {
    var temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

}

演示：http: //jsfiddle.net/Guffa/5sKdM/

我不确定这个大 O 是什么，但对于示例数据，它进行了 7 次比较和 2 次交换，所以这绝对比 O(n 2 ) 好。

另外，我不确定究竟什么算作“额外空间”，所以我不知道这是否满足一个额外空间的要求，但如果不满足，当前接受的答案也不...

于 2012-04-03T23:07:21.160 回答