-1

假设您有一个包含键值对的列表。键、值和对都不需要唯一。

下面的例子

a -> 1
b -> 2
c -> 3
a -> 3
b -> 1

将是有效的。

现在假设我想将另一个值 V 关联到任何键值对 (k->v)，它具有以下属性：

  • 两对相同，如果它们的密钥相同
  • 它由整个列表中的键值对集合唯一确定

这听起来很抽象，但例如 sum、maximum 和 count 函数可以作为示例

 Pair    SUM    MAX  COUNT
a -> 1    4      3     2
b -> 2    3      2     2
c -> 3    3      3     1
a -> 3    4      3     2
b -> 1    3      2     2

我正在寻找一种快速的方法/数据结构来计算整个列表中的此类函数。

如果键可以排序，则可以简单地对列表进行排序，然后遍历排序列表，并在每个块中使用相同的键计算函数 V。

我在问是否有很好的方法可以做到这一点，如果值不可比较或者不想更改条目的顺序。

一些想法：

  1. 当然，可以将哈希函数应用于键，以获得可排序的键。
  2. 当然，也可以存储每一对的原始位置，然后进行排序，然后计算函数，最后撤消排序。

所以基本上这个问题已经回答了。但是，我感兴趣的是是否有更优雅的解决方案可能使用一些适应数据结构

编辑：澄清 Sunny Agrawal 的评论，我所说的同事是什么意思。那么这也是如何很好地安排数据结构的问题的一部分。在我的示例中，我会得到另一个列表/映射，其中 (k->v) 作为键，V 作为值。但是，不以这种方式排列数据可能是有意义的。我要求，V 的存储方式是，对于给定的 k，它需要恒定的时间来获得 V。

4

1 回答 1

1

维持 2 个 DS

1. List< Pair< Key_Type, Value_Type > >
2. Map<Key_Type, Stats>

其中 Stats 的结构如下

struct Stats
{
    int Sum;
    int Count;
    int Max;
};

第一个 DS 按您要存储的顺序包含所有密钥、val 对，第二个维护每个密钥的数据统计信息，如您的示例所示

插入将按如下方式工作（伪 C++ 代码）

void Insert(key,val)
{
    list.insert(Pair(key,val))

    Stats curr;
    if(map.contains(key))
    {
        curr = map[key];
        curr.Max = Max(curr.Max, val);
        curr.Count++;
        curr.Sum += val;
    }
    else
    {
        curr.Max = val
        curr.Count = 1;
        curr.Sum = val;
    }
    map[key] = curr; 
}

更新列表的复杂度为 O(1)，更新地图的复杂度为 O(lgM)，其中 M 没有唯一键，如果 N 是列表中的对象总数，插入的总时间将为 O(N) + O(NlogM)

注意：如果我们只有插入，这将起作用，如果删除，更新 Max 将很困难

于 2013-10-07T14:51:03.573 回答