至少共享一个数字的一对数字的数量

Question

给定 n 个数字，您需要找到至少有一个数字相同的数字对数。

例如：对于 5 个数字：

2837 2818 654 35 931

答案: 6

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

我的尝试：我使用了一种结构，它存储了十进制数、数字数组形式和该数字的位数。

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

我的尝试是O(n^2)，速度较慢。是否有另一种算法可以更快地实现？

- L.ppt

---

你对一个值进行了哈希处理，但未能使用哈希表查找？ - leppie

我的解决方案在 n 较大时运行得很慢，但是结果是正确的。 - L.ppt

这个问题无法在O(n^2)以下的时间内解决，因为在最坏情况下至少需要O(n^2)的时间才能生成答案。 - Grigor Gevorgyan

@GrigorGevorgyan - 我猜问题中的示例答案应该是简单地6。你不必列出所有的配对。 - Jirka Hanika

@JirkaHanika 是的，你是正确的，展示了更多和清晰的解释，只需要计数作为答案，甚至在问题中也明确写着“成对数量”。 - L.ppt

Answer 1

重要的是要认识到哪些是变量，哪些是常数。

数字的位数是一个常数（10）。所有数字集合的数量也是一个常数（1024）。所有这些集合的对数也是一个常数（2的20次方，或者大约一百万）。让我们利用这个。

让我们尝试将输入预处理成一个“等效”的表示形式，在一个数据结构中存储。这个数据结构的大小是常数，与输入大小无关。无论我们用这个常数大小的结构做什么事情，都定义为常数时间操作，因此总运行时间在渐近意义下只由预处理阶段决定。

数据结构

创建一个包含1024个整数的数组，每个桶（索引）对应一个数字集合。我们想要在每个桶中存储确切包含该数字集合的输入数字数量。

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

算法

预处理很明显。取下一个数字（如'3'），将其转换为值（如3），现在计算相应的比特位（如1 << 3），并将其OR到一个（可能的）桶索引变量中。不同的数字占据不同的比特位，因此每个数字组合都获得一个唯一的桶，但我们摆脱了任何重复的数字。像这样循环，直到遇到数字分隔符；此时，桶索引是最终的，我们可以递增桶，重置桶索引，并跳过到下一个数字。

就是这样。所有需要做的就是数我们的羊。哎呀。一对一对的羊。

将每个桶与其他桶进行比较（但不包括自身）。每当两个索引共享一个数字时（可以使用“&”运算符确定），将这两个桶的内容相乘，并将产品添加到全局维护的总和中。

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

该总和即为结果。

性能

最坏情况：时间复杂度为O(n)，其中n是输入大小。

常数因子也是有利的。对于每个数字或分隔符，我们需要少量指令（和RAM访问）；并且常数阶段检查了一百万个桶对，每对花费大约另外几个指令（不需要RAM访问，数据结构非常紧凑）。这非常快速。

理论家会说这是作弊。我们假设输入长度没有上限（否则根本无法谈论渐近复杂度），但我们还假设可以将总输入长度放入整数变量中。哎哟。

更实际的程序员会注意到该算法在字母表大小方面呈指数级增长。我们很幸运；如果单词不是由数字组成而是由除分隔符外的任意字符组成，那么我们的算法仍然是一个渐近线性时间算法，但与能够轻松处理多兆字节输入的朴素算法相比，它将变得无法使用。

- Jirka Hanika

---

我认为这个形式与我的解决方案存在相同的问题，但这个问题可能是可以解决的。 - Jens Schauder

抱歉，我错了。我以为你会重复计算那些有多个数字相同的对，但实际上你没有这样做。 - Jens Schauder

请问您能否解释一下为什么使用2^0 + 2^3 + 2^6这种映射方法？我更想知道您是如何想到它的。 - gabber12

任何固定的映射都可以，只要它不会将两个不同的数字集映射到相同的代码。我选择这个映射是为了节省空间、友好缓存，并且易于在最后的嵌套迭代中使用：使用这个特定的映射，数组中没有“空洞”（有效代码之间没有非代码）。最后但并非最不重要的是，这种编码每个输入字符只需要少量的机器指令，在任何正常的架构上都不需要指数运算，因为对于任何x，2^x = 1 shift-to-left x。 - Jirka Hanika

@JirkaHanika，请详细解释一下，我没有完全理解上述解决方案，可以吗？拜托了。。 - pola sai ram

Answer 2

创建一个集合数组，每个数字对应一个集合。

遍历所有数字，将每个数字放入它所包含的集合中。

遍历所有10个集合，并将同一集合中的每个元素与其他元素组合。如果您不想在结果中得到(a,b)和(b,a)，则可与比自己大的其他元素组合。

我认为这仍然是O(n ^ 2)，但可以使用fork join方法很好地并行化。

更新

刚刚意识到您只需要结果的数量。因此，对于所有集合，应该将其大小* size-1求和。由于插入集合并获取其大小应该是线性的（我认为），因此这实际上可能是O(n)。

另一个更新

如果您的数字是唯一的，并且只关心成对数目，则根本不需要集合，只需要计数器即可。

不起作用

来自评论：

Consider 1st pair in above questions test case (2837,2818), this will put first number in set containing digit 2 and 8 and same for 2818 now they are to be counted as one but counting in 2 and 8 will count it twice. I hope you understand what I am trying to say...

所以这种方法行不通...我猜它可能对其他人有价值作为警示。

- Jens Schauder

---

枚举这些对，而不仅仅是计算它们的数量，在最坏情况下必然需要Ω(n²)的时间，因为它们的数量是O(n²)。 - Fred Foo

@larsmans 您是正确的，我刚意识到只需要成对的数量。已编辑答案。 - Jens Schauder

@L.ppt，您说的数字非常大是什么意思？您是指n可以非常大吗？还是说每个数字都可以非常大？如果n可以高达10^18，我想您会遇到问题。 - Jens Schauder

@L.ppt：哪个十进制数字（不是数字！）比9大？ - fork0

所以这些数字最多有18位数...由于这只是O()估计中的常数，而且不是很大，因此它几乎无关紧要。 - Jens Schauder

@JensSchauder 考虑上述问题测试用例中的第一对（2837,2818），这将把第一个数字放入包含数字2和8的集合中，2818同理。现在它们应该被视为一个计数，但是在2和8中进行计数会使其计算两次。我希望你明白我想说什么... - L.ppt

Answer 3

首先，我注意到常见数字的位置并不重要。

在这种情况下，我使用哈希表草拟了一个小算法：形成10个箱子，每个数字对应一个箱子。然后，对于每个数字，将该数字的ID唯一地放入其所具有的每个数字对应的箱子中。此操作的时间复杂度为O(n*k)，其中k是数字的位数。最后，为了形成所有的数字对，从每个箱子中取出数字对。为了去除可能的重复项，将每个数字对(a,b)与a进行排序。

我认为最坏的情况实际上是O(n^2)；事实上，我认为这一步骤的复杂度必须是O(n^2)，因为您想要获取所有的数字对（最多n*(n+1)/2）。因此，最终的复杂度确实是二次方的。

- Bentoy13