重要的是要认识到哪些是变量,哪些是常数。
数字的位数是一个常数(10)。所有数字集合的数量也是一个常数(1024)。所有这些集合的对数也是一个常数(2的20次方,或者大约一百万)。让我们利用这个。
让我们尝试将输入预处理成一个“等效”的表示形式,在一个数据结构中存储。这个数据结构的大小是常数,与输入大小无关。无论我们用这个常数大小的结构做什么事情,都定义为常数时间操作,因此总运行时间在渐近意义下只由预处理阶段决定。
数据结构
创建一个包含1024个整数的数组,每个桶(索引)对应一个数字集合。我们想要在每个桶中存储确切包含该数字集合的输入数字数量。
例如,3606有数字0、3和6,所以它会被计入第20+23+26=73个桶中。
算法
预处理很明显。取下一个数字(如'3'
),将其转换为值(如3
),现在计算相应的比特位(如1 << 3
),并将其OR到一个(可能的)桶索引变量中。不同的数字占据不同的比特位,因此每个数字组合都获得一个唯一的桶,但我们摆脱了任何重复的数字。像这样循环,直到遇到数字分隔符;此时,桶索引是最终的,我们可以递增桶,重置桶索引,并跳过到下一个数字。
就是这样。所有需要做的就是数我们的羊。哎呀。一对一对的羊。
将每个桶与其他桶进行比较(但不包括自身)。每当两个索引共享一个数字时(可以使用“&”运算符确定),将这两个桶的内容相乘,并将产品添加到全局维护的总和中。
也将每个桶与其自身进行比较,并仅将
x * (x-1) / 2
添加到全局维护的总和中,其中
x
为桶的内容。
该总和即为结果。
性能
最坏情况:时间复杂度为
O(n)
,其中
n
是输入大小。
常数因子也是有利的。对于每个数字或分隔符,我们需要少量指令(和RAM访问);并且常数阶段检查了一百万个桶对,每对花费大约另外几个指令(不需要RAM访问,数据结构非常紧凑)。这非常快速。
理论家会说这是作弊。我们假设输入长度没有上限(否则根本无法谈论渐近复杂度),但我们还假设可以将总输入长度放入整数变量中。哎哟。
更实际的程序员会注意到该算法在字母表大小方面呈指数级增长。我们很幸运;如果单词不是由数字组成而是由除分隔符外的任意字符组成,那么我们的算法仍然是一个渐近线性时间算法,但与能够轻松处理多兆字节输入的朴素算法相比,它将变得无法使用。
6
。你不必列出所有的配对。 - Jirka Hanika