聚点算法

Question

我有一个表评

• row1 = (V1，K1，5);
• row2 = (V2，K2，7);
• row2 = (V1，K1，3);

我需要聚合AggregateRating表中的点，以便该表包含

• row1 = (V1，K1，8);
• row2 = (V2，K2，7);

我循环一次通过评级表并创建一个带key = (Col1，Col2)的映射，如果键存在，则value = Points -如果存在，则添加其他的点数，创建一个新的地图条目。评等表可以包含接近100+条目的内容，因此我希望避免多次传递。

，这是最有效的方法吗？

Answer 1

这取决于用来存储地图的数据结构。如果您使用哈希映射，而不是存储和读取它将是常数的复杂性(O(1))。然后，使用一个查询进行一次传递，最多对数组中的每个条目进行一次插入。这意味着算法的整个复杂性将是O(n)。

但是，仅输入是O(n)，这意味着您不能做得更好。

请记住，如果您选择不同的映射实现，例如树形映射，复杂性将发生变化，您将无法得到最有效的解决方案。