2

如果我有一系列项目：

1, 2, 3, 4, 5, 6, 7, 8

我想选择一系列项目并将它们移动到数组中的另一个位置。例如：

1, 2, 5, 6, 7, 3, 4, 8

此处 5、6、7 段已移至索引 2。

这样做的最有效方法是什么，特别是限制额外数组副本的数量。我有一个可用的版本，但它效率低下，并且在我试图优化的算法中发挥核心作用。

谢谢。

4

4 回答 4

3

尝试使用链表。由于您正在移动列表的子部分，因此移动子列表两端的引用比复制同一子列表中的每个单独项目更节省内存。总体时间复杂度是相同的（Θ(n) 遍历链表，Θ(n) 复制数组段），但你会有更好的内存复杂度（常数 n 与 Θ(n) 相对）和持续内存分配/释放的问题更少。

于 2013-05-30T23:30:47.740 回答
2

一种方法是切出应该移动的项目，然后移动现有成员：

// T[] source
// int dest
// int start, end
T[] slice = new T[end - start];
Array.Copy(source, start, slice, 0, slice.Length);

if (dest < start)
{
    // push towards end
    Array.Copy(source, dest, source, dest + slice.Length, start - dest);
}
else
{
    // push towards start
    // who moves where? Assumes dest..dest+count goes left
    Array.Copy(source, end, source, dest, dest - start);
}

Array.Copy(slice, 0, source, dest, slice.Length);
于 2013-05-30T22:57:42.540 回答
1

我知道你已经选择了答案；但这个问题真的让我很敏感；看看是否可以用另一种方式编写它。

所以我想出了这个代码：

static int[] MoveSlice(int[] arr, int startIndex, int length, int newIndex)
{
    var delta = (int)Math.Abs(newIndex - startIndex);

    if (delta >= length)
    {
        for (var i = 0; i < length; i++)
        {
            var swap = arr[startIndex + i];
            arr[startIndex + i] = arr[newIndex + i];
            arr[newIndex + i] = swap;
        }
    }
    else
    {
        var newStart = newIndex + length;

        for (var i = 0; i < delta; i++)
        {
            var swap = arr[newStart + i];
            arr[newStart + i] = arr[newIndex + i];
            arr[newIndex + i] = swap;
        }

        var l = (int)Math.Abs(length - delta);
        arr = MoveSlice(arr, newIndex + delta, l, newIndex);
    }

    return arr;
}

我还没有测试性能。但我喜欢解决它！

也许您需要使用更多代码来检查边界等可能出现的错误。

于 2013-06-02T00:43:01.640 回答
0

如果您想避免为了提高效率而制作数组副本，您可以完全避免它们。您可以对单个值使用最少的变量来将项目移动到它们的新目的地。这样的算法在内存上非常有效，并且总体上也很有效，尽管它显然不能利用本地高效的数组复制。

于 2013-05-31T10:58:53.780 回答