algorithm - 找到最常出现的对

Question

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

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

我有兴趣查找至少供应 k Material 的供应商列表，特定供应商说 Supplier_1 供应这些 Material 。

我能想到的一种方法是将所有供应商与 Supplier_1 配对，每种 Material 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 的 Material 放在一个哈希集中，这样您就可以在恒定时间内验证任何 Material 是否由Supplier_1 提供。

一旦你有了，你就可以再次迭代数据，并在字典( HashMap )中为每个供应商保留一个计数，每次 Material 在上述集合中时你都会递增。

在 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 种 Material 。

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