用于检测在长列表中出现的对的算法

Question

给出一长串N(不必要的不​​同)数字,比如说

{1, 50, 3, 99, 1, 2, 100, 99, 4, 100, 4, 100} (could be very long)

比方说,还有一小组M个有序对

(1, 2)

(2, 1)

(1, 3)    

(99, 50)

(99, 100)

我想检测有序对是否出现在列表中的任何位置(它们可以分开,但顺序很重要).例如,上面的计数将是:

(1, 2): 2 (each 1 pairs with the later 2)

(2, 1): 0 (no 1's come after the 2)

(1, 3): 1 (only one of the 1's come before the 3)

(99, 50): 0 (no 99's come before the 50)

(99, 100): 5 (3 times for the first 99 and 2 times for the second)

假设有序对中的每个数字都保证出现在列表中,是否存在一种算法来提取这些计数的速度比天真的O(N*M)时间更快(通过强力搜索每个有序对来实现)？

作为一个附带问题,如果我们仅限于布尔出现而不是计数,那么可能会有一个快速算法吗？那是:

(1, 2): yes

(2, 1): no

(1, 3): yes

(99, 50): no

(99, 100): yes

任何帮助,将不胜感激.

Answer 1

保留两个哈希值,一个将数字映射到它们出现的最小位置,一个映射数字到它们出现的最大位置.如果至少[a] <最大[b](并且两个散列键都存在),则有序对(a,b)按顺序出现.预处理时间是线性的,空间使用是线性的,查询时间是恒定的(在关于散列的复杂性的标准假设下).

至于计数版本,我能想到的最好的是保持一个哈希将每个数字映射到它按排序顺序出现的位置.要查询一对,"合并"位置列表,跟踪到目前为止的a元素的数量和对的出现次数.当选择b元素作为下一个时,将对数增加a元素的数量.当选择a元素为next时,增加a元素的数量.(如果a == b,返回长度选择2.)