查找最常出现的对

Question

假设我有一个列表(或数组)，它将供应商与他们提供的材料联系起来。例如，表单的数组

[[Supplier_1, Material_a], [Supplier_2, Material_a], [Supplier_3, Material_a], [Supplier_1, Material_b], [Supplier_2, Material_c], [Supplier_3, Material_b], ...]

我感兴趣的是查找至少提供某一特定供应商所说的Supplier_1供应的k材料的供应商列表。

我能想到的一种方法是为Supplier_1供应的每种材料将所有供应商与Supplier_1配对

[[Supplier_1, Supplier_2, Material_a], [Supplier_1, Supplier_3, Material_a], [Supplier_1, Supplier_3, Material_b]...]

然后计算每一对出现的次数

[[Supplier_1, Supplier_2, 1], [Supplier_1, Supplier_3, 2]...]

问题是，这种方法可能非常耗时，因为提供的列表可能非常长。我想知道是否有更好的方法来做这件事。

Answer 1

您可以将Supplier_1的材料放在一个散列集中，这样就可以验证任何材料是否由Supplier_1在固定时间内提供。

一旦有了它，你就可以再次迭代数据，并在字典(哈希图)中保留每个供应商的计数，每次材料在上面提到的集合中时，该计数都会增加。

在Python中，它看起来像这样：

def getsuppliers(pairs, selected_supplier, k):
    materialset = set()
    countmap = {} # a dictionary with <key=supplier, value=count> pairs
    for supplier, material in pairs:
        if supplier == selected_supplier:
            materialset.add(material)
        countmap[supplier] = 0

    # An optional quick exit: if the selected provider does not have k materials,
    #   there is no use in continuing...
    if countmap[selected_supplier] < k:
        return [] # no supplier meets the requirement

    for supplier, material in pairs:
        if material in materialset:
            countmap[supplier] = countmap[supplier]+1

    result = []
    for supplier, count in countmap.items():
        if count >= k:
            result.append(supplier)

    return result

注:这也包括选定的供应商，前提是它至少有k种材料。

每个单独循环体中的所有操作都具有恒定的时间复杂度，因此总体时间复杂度为O(n)，其中n是输入列表(pairs)的大小。