algorithm - 至少共享一个数字的对数

Question

给你n 个数字，你必须找到对数，使得它们之间至少有一个数字是公共(public)的。

例如。对于 5 个数字:

2837 2818 654 35 931

答案:6

这里的对是(2837,2818), (2837,35), (2837,931), (2818,931), (654,35), (35,931)

我的尝试:我采用了一种结构来存储十进制数、数组中数字形式的数字以及该数字中的位数。。。 p>

现在，对于每个数字，我散列数组中包含索引0-9的数字，并检查所有后续数字是否已经存在任何数字。

我的尝试是O(n^2)，这很慢。是否有另一种算法可以更快地工作？

Answer 1

了解这里的变量和常量是至关重要的。

位数是常数 (10)。所有数字组的数量 (1024) 也是如此。所有此类集合对的数量也是如此(2²⁰，或大约一百万)。让我们充分利用这一点。

让我们尝试将输入预处理为大小恒定(与输入大小无关)的数据结构中的“等效”表示。根据定义，我们随后对该恒定大小结构所做的任何操作都是恒定时间操作，因此总运行时间仅由预处理阶段渐近确定。

数据结构

创建一个包含1024个整数的数组，每个桶(索引)对应一组数字；我们希望在每个桶中存储恰好具有该组数字的输入数字的数量。

例如，3606 有数字 0、3 和 6，所以它会被计入桶 2⁰ + 2³ + 2⁶ = 73.

算法

预处理很明显。获取下一个数字(例如 '3' )，将其转换为其值(例如 3 )，现在计算相应的位(例如 1 << 3 )并将其或运算为(暂定的)桶索引变量；不同的数字位于不同的位，因此每个数字组合都有一个唯一的桶，但我们去掉了任何重复的数字。如此循环直到遇到数字分隔符；那时，桶索引是最终的，我们可以增加桶，重置桶索引并跳到下一个数字。

就是这样。剩下的就是数我们的羊。哎呀。成对的绵羊。

将每个桶与其他桶(但不是它本身)进行比较。每当两个 索引 共享一个数字(这可以使用 & 运算符确定)时，将这两个桶的内容相乘，并将乘积添加到全局维护的总和中。

将每个桶也与自身进行比较，只添加 x * (x - 1) / 2到全局维护的总和，其中 x是桶的内容。

那个总和就是你的结果。

性能

最坏情况:O(n)其中 n是输入大小。

常数因素也是有利的。我们需要每个数字或分隔符的少量指令(和 RAM 访问)； constant 阶段检查一百万个桶对，在每对桶上花费一些类似的指令(不需要 RAM 访问，数据结构非常紧凑)。这快如闪电。

理论家会说这是作弊。我们假设输入长度没有上限(或者我们根本不能谈论渐近复杂性)，但我们还假设我们可以将总输入长度放入一个整数变量中。哦，好吧。

更实际的程序员会注意到该算法的字母大小呈指数级增长。我们很幸运；如果我们的单词不是由数字组成，而是由除分隔符以外的任意字符组成，我们的算法仍然是渐进的线性时间算法，但与可以轻松处理高达兆字节的朴素算法相比，它对于任何输入都慢得无法使用一次输入。