7

我正在寻找一种允许将值快速（比 O(N) 快）任意插入到结构中的数据结构（类似数组）。数据结构必须能够以插入的方式打印出其元素。这类似于 List.Insert() 之类的东西（它太慢了，因为它必须移动每个元素），除了我不需要随机访问或删除。插入将始终在“数组”的大小范围内。所有的价值观都是独一无二的。不需要其他操作。

例如，如果 Insert(x, i) 在索引 i（0 索引）处插入值 x。然后：

  • Insert(1, 0) 给出 {1}
  • Insert(3, 1) 给出 {1,3}
  • Insert(2, 1) 给出 {1,2,3}
  • Insert(5, 0) 给出 {5,1,2,3}

并且它需要能够在最后打印出 {5,1,2,3}。

我正在使用 C++。

4

7 回答 7

9

使用跳过列表。另一种选择应该是分层向量。跳过列表在 const O(log(n)) 处执行插入并保持数字有序。分层向量支持在 O(sqrt(n)) 中插入，并且可以再次按顺序打印元素。

编辑：根据 amit 的评论，我将解释如何在跳过列表中找到第 k 个元素：

对于每个元素，您都有一个指向下一个元素的链接的塔，并且对于每个链接，您都知道它跳过了多少个元素。因此，寻找第 k 个元素，您从列表的头部开始，沿着塔向下，直到找到一个跳过不超过 k 个元素的链接。您转到该节点指向的节点，并随着您跳过的元素数量减少 k。继续这样做，直到你有 k = 0。

于 2012-04-06T12:37:49.543 回答
1

您是否考虑使用std::map or std::vector？

您可以使用std::map带有插入等级的 a 作为键。并且vector有一个reserve成员函数。

于 2012-04-06T12:37:17.340 回答
1

关于您的评论：

List.Insert() （这太慢了，因为它必须移动每个元素），

列表不会改变它们的值，它们会遍历它们以找到你想要插入的位置，小心你说的话。这可能会让像我这样的新手感到困惑。

于 2012-06-05T18:46:33.283 回答
1

您可以使用std::map映射（索引，插入时间）对到值，其中插入时间是“自动增量”整数（在 SQL 术语中）。对的排序应该是

(i, t) < (i*, t*)

当且当

i < i* or t > t*

在代码中：

struct lt {
    bool operator()(std::pair<size_t, size_t> const &x,
                    std::pair<size_t, size_t> const &y)
    {
        return x.first < y.first || x.second > y.second;
    }
};

typedef std::map<std::pair<size_t, size_t>, int, lt> array_like;

void insert(array_like &a, int value, size_t i)
{
    a[std::make_pair(i, a.size())] = value;
}
于 2012-04-06T12:49:35.833 回答
1

GCC 默认包含的一个解决方案是绳索数据结构。这是文档。通常，在处理长字符串时会想到绳索。这里我们用ints 而不是字符，但它的工作原理是一样的。只需int用作模板参数。（也可以是pairs 等）

这是Wikipedia 上对绳索的描述。

基本上，它是一棵二叉树，它维护左右子树中有多少元素（或等效信息，即所谓的顺序统计信息），并且当插入和删除元素时，这些计数会随着子树的旋转而适当更新。这允许 O(lg n) 操作。

于 2016-05-05T12:00:42.450 回答
0

有这种数据结构将插入时间从 O(N) 缩短到 O(sqrt(N))，但我并没有那么印象深刻。我觉得一个人应该能够做得更好，但我必须努力工作。

于 2021-11-04T20:44:51.700 回答
-1

In c++ you can just use a map of vectors, like so:

int main() {
  map<int, vector<int> > data;
  data[0].push_back(1);
  data[1].push_back(3);
  data[1].push_back(2);
  data[0].push_back(5);
  map<int, vector<int> >::iterator it;
  for (it = data.begin(); it != data.end(); it++) {
    vector<int> v = it->second;
    for (int i = v.size() - 1; i >= 0; i--) {
      cout << v[i] << ' ';
    }
  }
  cout << '\n';
}

This prints:

5 1 2 3

Just like you want, and inserts are O(log n).

于 2012-04-06T12:46:31.320 回答