在快于O(n^2)的时间内，使用O(1)额外内存重新排列数组

Question

假设我有以下数组：

1, 4, 5, 2, 3

我需要重新排列它

5, 1, 4, 2, 3

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

我找到了一个解决方案。但它的时间复杂度是 O(n^2)。

有人能提供更快的解决方案吗？

谢谢

编辑：

抱歉，这不是旋转数组。

我需要将原始数组更改为结果数组。 顺序可以任意。 我只需要使 A -> B。 B 已经告诉我了。

谢谢

第二次编辑：

让它更清晰。 数组 B 不是固定的。 我们需要找到一般解决方案。

更新：

谢谢大家。看起来这是一道脑筋急转弯题目。哈哈 :D

我的朋友被亚马逊面试官问到了这个问题。LOL

- Anders Lind

---

那里的转换是什么？我看不出它是任何一种排序。你是如何从原始数据得到输出的呢？（我理解去除空格，只是顺序我不明白。） - Corbin

据我理解，根据需求需要实现将某个地址存储某个值的功能。 - Anders Lind

我认为你无法得到比O(n^2)更好的结果。 - Saeed Amiri

你能更具体一些吗？你能举个例子吗？ - Shahbaz

如果B已知，则不需要任何工作，因此显然这是O（1）。 - Oliver Charlesworth

等一下，如果给你 B，为什么还需要从 A 重新创建它？ - Shahbaz

Answer 1

我觉得这只是对数组进行排序的特殊情况，排序顺序相当任意。因此，最优算法的时间复杂度应为O(n log n)，使用一种原地排序的算法（牺牲稳定性）则空间复杂度为O(1)。原地合并排序和原地快速排序都符合要求，如果平均 O(n log n) 可以接受的话。

- mpdonadio

---

实际上，O(1)空间让您执行swap(a,b)操作。 - ninjagecko

@ninjagecko，你甚至可以使用O(0)空间来交换a和b。 - Shahbaz

@Esailija，0是O（0），因为存在一个c> 0（比如1），其中对于所有输入大小n> 0，都有0 < c * 0。请注意，我们谈论的是内存，而不是时间。 - Shahbaz

@Shahbaz 我同意。我只是认为ninjagecko也知道这一点，并想通过实践来相对化（嗯，这是一个真正的词吗？）O(0)。当然，我可能是错的。 - Daniel Fischer

@ninjagecko，那并不完全正确。即使a+b溢出，从a-b中的下溢也会修复它。毕竟，加法和减法在模2^32（如果是32位）下是同余的，最终数字将是正确的。尽管如此，这是人们选择异或运算符而不是其他运算符的另一个原因。（附：BugFix：在我的第一条评论中，“a $ b = b $ a（与#相同）”不需要保持） - Shahbaz

Answer 2

这个解决方案使用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。

- fwenom

---

你的意思是通过 source.index(dest[i]) 进行线性搜索？那样会导致 O(n^2) 的性能。 - Shahbaz

啊，我没有读完整个问题。只看了O(1)空间的部分。好吧，至少这是一个可行的解决方案，供其他人查看和改进。太糟糕了，我不能只做 a,b = b,a。 - fwenom

Answer 3

看起来你只是将前三个元素向左移动（带环绕）。

所以，忽略索引3和4。

  int temp = array[0]
  array[0] = array[1]
  array[1] = array[2]
  array[2] = temp

- Justin

Answer 4

你可以这样做：

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²)更好。

此外，我不确定什么样的“额外空间”算是符合要求，所以我不知道这是否满足一个额外空间的要求，但如果不满足，那么目前被接受的答案也不符合要求...

- Guffa

---

如果这确实是预期的答案，那么这将是我至今听过的最愚蠢的面试问题 :) :) :) - Sergey Kalinichenko

抱歉，澄清一下我的问题。不是旋转数组。 - Anders Lind

这是实现PostScript滚动命令所需的代码的特殊情况，该命令需要两个参数 - 从堆栈顶部滚动的元素数量以及向前（向后）滚动它们的位置数量。 - DRVic