0

假设有一个数字列表 -存储在数组、队列、链表或任何支持列表数据结构的东西中（即数字序列很重要）。现在，假设我们想在将一个数字添加到现有列表后添加一个新对象（list.add()）。但是， list.add() 接受原始列表并返回一个新列表，其中包含原始列表中的数字和新数字。函数 add() 不会以任何方式更改原始列表对象。

因此，要实现这种方式，我们在函数中复制原始列表，将新数字添加到其中，然后返回它。这需要 O(n) 时间。

那么有没有其他方法可以在比 O(n) 更短的时间内完成这项工作。

编辑 1：该元素将在最后添加。add() 返回的对象应该包含原始列表中的所有数字和新的数字。原始列表保持不变。

编辑 2：我认为，如果我们每次向列表中添加数字时不复制整个列表，这可能是可能的。在这方面有没有可能？

4

3 回答 3

0

不确定您需要支持哪些其他类型的功能，但如果add是您关心的唯一方法，您可以创建一个包装类，该类基本上维护一个新列表，该列表表示您要添加到原始列表中的部分。然后，lookup进入这个包装类会考虑原始列表和新列表的连接。

下面是一些示例伪 C# 代码：

public class ListWrapper
{
    private ArrayList<T> Original;
    private ArrayList<T> ConcatenatedPortion;

    public ImmutableList(ArrayList<T> original)
    {
        Original = original;
        ConcatenatedPortion = new ArrayList<T>();
    }

    public bool Add(<T> element)
    {
        return ConcatenpatedPortion.Add(element);
    }

    public <T> Get(int index)
    {
        if (index < 0) throw new IndexOutOfBoundsException();

        if (index < Original.Length)
            return Original.Get(index);

        int newIndex = index - Original.Length;

        if (newIndex < ConcatenatedPortion.Length)
            return ConcatenatedPortion.Get(newIndex);

        throw new IndexOutOfBoundsException();
    }
}
于 2013-01-18T21:39:18.820 回答
0

为什么要复制？

您可以在 O(1) 中添加到列表或数组的末尾

基本上只需添加后面的数字并使用相同的参数并将大小增加 1，然后创建一个列表对象，这就是 O(1)

于 2013-01-15T18:40:19.263 回答
0

附加到链表的头部将是 O(1)。

或者，支持随机插入是最近大量研究的主题。Clojure 和 Scala 使用类似于Hash 数组映射的 trie的东西，除了一个不可变的变体，它允许通过仅复制受 O(logn) 中更新影响的分支来更快地更新。当分支因子很高（即 32）时，这也允许有效地进行持续查找。

于 2013-01-15T18:38:15.187 回答