将元素插入到排序数组并查找其索引的最有效方法-Java 学习之路

我需要在排序范围内插入一个元素，但我还需要知道它的索引（范围内的元素数量少于元素） . 我想在 O(logN) 时间这样做 . 我可以用基本的C容器做到这一点吗？

我正在考虑使用 std::multimap ，使用此容器我可以将元素插入到具有O（logN）复杂性的位置 . 但是要获取索引，我需要调用std :: distance，它需要进行O（N）操作，因为multimap迭代器不是随机访问 .

另一种方法是使用已排序的 std::vector 和 std::binary_search 算法 . 在这种情况下，搜索采用O（logN），但插入将采用O（N）操作，因为向量中间的插入是线性操作 .

那么，是否有std / boost容器可用于达到结果，或者我需要为此实现自己的结构？谢谢！

2 回答

你可以使用Boost.MultiIndex的ranked indices：

Live Coliru Demo

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ranked_index.hpp>
#include <boost/multi_index/identity.hpp>

using namespace boost::multi_index;
using ranked_int_set=multi_index_container<
  int,
  indexed_by<
    ranked_unique<identity<int>>
  >
>;

#include <iostream>

int main()
{
  ranked_int_set s={0,2,4,6,8,10,12,14,16};

  auto it=s.insert(9).first;
  std::cout<<"9 was inserted at position #"<<s.rank(it)<<"\n";
  std::cout<<"14 is located at position #"<<s.find_rank(14)<<"\n";
}

产量

9 was inserted at position #5
14 is located at position #8

回复于 2024-04-25T10:20:30+08:00

3

不，我找了 .

有一种方法可以实现这一点 . 从二叉树或跳过列表开始，并保持子树/跳过的大小（一些额外的开销 - 当插入项目时，您必须回溯到父项/跳过并递增，并且类似于删除） .

然后你可以在lg n时间内获得索引，随机访问（按索引或偏移量）lg n时间，并保持同时排序 .

我试图找到一个预先写好的容器来做这件事是徒劳的，而且这个项目是 jar 装的，所以我没有去写它 .

可以使用完整数据库，对已排序的列进行索引，并且您可能能够以合理的速度快速获得该数字 .

可能的情况是，如果一个简单的线性排序向量是不合理的（使用其昂贵的插入中间），您可能无论如何都要考虑数据库 .

作为看起来很有希望但失败的容器的示例，Boost的MultiIndex容器允许您以多种方式索引容器，但顺序索引和有序索引是独立的 . 因此，您可以告诉您插入项目的顺序，以及排序之前/之后的位置，而不是排序中的索引 .

回复于 2024-04-25T10:20:30+08:00

将元素插入到排序数组并查找其索引的最有效方法

2 回答

相关问题