快速选择至少有k个元素与主阵列相同的阵列

Question

我有N独特元素，索引从0开始，以及使用这些元素创建的数组的数据库。数据库是不变的，不会改变。给出一个查询数组，对于每个调用都是不同的。

我必须选择与查询数组至少有K元素（例如一半）的db数组。

一种解决方案我认为：具有长度N的位阵列，设置对应于查询堆元件，并通过整体分贝行走一次，滤除阵列与< K比特。这是很可扩展性，但也有点慢，更快的方法似乎是可能的......

注：

• 查询阵列可以有元素不出现在任何数据库阵列。
• 没有数组（数据库或查询）有重复的元素。
• 可以在db数组上进行预处理，以便使某些操作更快，并根据需要为内存提供速度。

Answer 1

使用的倒排索引。

这是搜索引擎为寻找匹配查询所做的事情。

Answer 2

如果数据库已修复，那么您可以构建一个包含项目和数组的表格。所以，如果你有两个数组：

A = {1, 7, 9, 12, 15} 
B = {7, 12, 15} 

你的表是：

Item Array 
    1  A 
    7  A 
    7  B 
    9  A 
12  A 
12  B 
15  A 
15  B 

这本质上是一个反向指标。

现在，给定查询数组{1, 5, 7, 12}，您可以查询数据库中的所有这些项目。

select * from ItemArrayIndex where Item in (1, 5, 7, 12) order by Array 

然后计算每个阵列有多少项目。

想一想，如果按照数组进行分组，您可能可以从SQL查询中获取计数。虽然我的SQL有点生疏。 。 。