arrays - 如何在数组数组中查找某些数组

Question

我有一个数组数组。示例:

[
 [a, b, c],
 [b, d],
 [a, c],
 [b],
 [a, b, c, d]
]

在实践中，内部数组会相对较短，但外部数组将有几千行。

现在，我有一个引用数组。示例:

[a, b, c]

挑战在于确定第一个数组的哪些行完全包含在引用数组中。对于此示例，我希望第 1、3 和 4 行在此检查后返回给我。

我可以使用嵌套循环很容易地做到这一点，但我想知道是否有一种更可扩展的聪明算法。

回顾:我需要作为引用数组的某个子集的行号。行元素不一定是唯一的。编辑:每个数组中可以包含大约 200 个唯一元素。数组的数组将是常量，但我需要对许多不同的引用数组执行相同的搜索

Answer 1

如果您将引用数组存储为一个结构，您可以在 O(1) 时间内检查元素的成员资格(例如，使用哈希表或仅使用 0/1 成员资格指示器数组，因为宇宙很小)，然后你可以将你的数组集合存储为一个 trie 树，其中每个数组都被排序，并遍历 trie 查找路径到完全包含在你的引用数组中的叶子。这可以降低复杂性，因为当子集合中的数组重叠时，您将使用 trie 中更高层的单个比较同时遍历数组的子集合，并且当它们包含一个公共(public)元素时，您将同时跳过数组的子集不在您的引用数组中。