java - 具有名称和数字的列表的最快搜索算法是什么

Question

该列表有名称和编号。每个名字都有一个数字。该列表按名称排序，列表中的数字从最小到最大排序。我需要找到与每个 name关联的所有最大数字的总和。

a 1, a 4, a 5, b 0, b 4, c 1, n 9, n 10

我需要输出

5 + 4 + 1 + 10 = 20

我需要在O(logn)时间内完成此操作。

标签： javaalgorithmperformancesorting

Answer 1

伪代码，找到每个名字 O(M) 的最后一个 O(log N)。

auto it = vec.begin();
while (it != vec.end()) { // O(M)
  auto last = find_last_with_same_name(it, it->name); 
  sum += last.value;
  it++;
}

使用指数搜索 O(log N) 来查找最后一个因此是最大值。

总共 O(M log N)。

如果 M，名字的数量是一个常数，你得到 O(log N)，但这需要一些规则律师。