时间戳

首页 > 解决方案 > 数组将相邻元素的块移动到新索引

arrays - 数组将相邻元素的块移动到新索引

问题描述

问题

问题很简单，想象一下我有一个列表或一个array（不是linkedList）

list = [1, 2, ... 999999]

现在我想将元素从索引 3000 移动到 600000 到索引 100。结果应该很容易想象

[1, 2,... 99, 100, 3000, 3001, ... 6000000, 101, 102, ...2999, 600001, 600002, ... 999999]

那些操作怎么做efficiently？

判断我的想法

免责声明：您可以说此操作与将 101 移动到 2999 到索引 600000 完全相同。这似乎是一种更有效的操作。但这不是我的问题所涉及的算法，我的问题是关于如何更有效地移动，所以让我们做最初的问题。

我可以想到几种方法：

  1. 只需对元素 3000 到 600000执行delete和。（时间复杂度是多少？）insert
  2. 将元素从 [3000, 600000] 保存到临时空间，然后用于delete insert将所有内容从 [101 到 2999] 移动到 [597192, 600000] 以腾出空间将 [3000, 600000] 传输回索引 100。临时保存来自[3000, 600000] 会消耗一些内存，但是复制会使整个操作变慢吗？（时间复杂度？）
  3. 是一种改进的尝试 2. 相同的想法，但移动操作不是由 完成的delete insert，而是通过手动将 [101,2999] 复制到 [597192, 600000]。（时间复杂度？与 相比，它是否提高了速度delete insert）？
  4. 是改进 2 或 3 的尝试。相同的想法，但没有delete insert，但使用了很多复制。但不是从 [3000, 600000] 复制所有内容，而是一次仅在临时内存中保存 1 个元素，并以复杂的方式移动/复制所有内容。（这比别人快吗？有可能实现吗？你能告诉我代码/伪代码）

有更好的想法吗？

感谢您的阅读和思考。

标签： arraysalgorithm

解决方案

您所追求的算法称为rotate. 有两种常见的实现方式。两者都在O(length)时间和O(1)空间上运行。

一个归功于 Dijkstra，从某种意义上说，它最终是有效的，因为每个元素只移动一次。实现起来有点棘手，并且需要不明显的设置。此外，它可能会以非常不友好的缓存方式运行。有关详细信息，请参阅方法 3（一种杂耍算法）。

另一个非常简单，缓存友好，但将每个元素移动两次。[l, r)要围绕中点旋转范围，m请执行

    reverse(l, m);
    reverse(m, r);
    reverse(l, r);

推荐阅读