你得到了n数字,你必须找到对的数量,使得它们之间至少有一个数字.
例如.对于5个数字:
2837 2818 654 35 931
答案:6
这里的配对是 (2837,2818), (2837,35), (2837,931), (2818,931), (654,35), (35,931)
我的尝试:我采用的结构存储了十进制数字,数字形式的数字和数字中的数字.
现在,每一个号码,我散列这个数字在阵列conatining指数0-9,并与所有下面的数字选中的阉他们的任何一位的是已经存在.
我的尝试是O(n^2),这很慢.还有其他算法可以更快地运行吗？
Jir*_*ika 12
了解变量是什么以及这里的常量是至关重要的.
位数是常数(10).所有数字组的数量也是如此(1024).所有这些对的数量也是如此(2 20,或大约一百万).让我们利用这一点.
让我们尝试将输入预处理为大小恒定的数据结构中的"等效"表示(与输入大小无关).无论我们如何处理这种恒定大小的结构,定义为恒定时间操作,因此总运行时间仅由预处理阶段渐近确定.
数据结构
创建一个1024个整数的数组,每个桶(索引)对应一组数字; 我们想要存储每个桶中具有该组数字的输入数字的数量.
例如,3606具有数字0,3和6,因此它将在桶2 0 + 2 3 + 2 6 = 73中计数.
算法
预处理是显而易见的.取下一个数字(例如'3'),将其转换为其值(例如3),现在计算相应的位(例如1 << 3)并将其转换为(暂定的)桶索引变量; 不同的数字位于不同的位,所以每个数字组合都有一个独特的桶,但我们摆脱了任何重复的数字.像这样循环直到遇到数字分隔符; 在那时,桶索引是最终的,我们可以只增加桶,重置桶索引并跳到下一个数字.
而已.剩下的就是数数我们的羊.哎呀.成对的羊.
将每个桶与每个桶进行比较(但不是自身).只要两个索引共享一个数字(这可以使用&运营商确定),将这两个桶的内容相乘,并将产品添加到全局维护的总和中.
将每个存储桶也与自身进行比较,并仅添加x * (x - 1) / 2到全局维护的总和,其中x是存储桶的内容.
这笔钱是你的结果.
性能
最坏的情况:输入大小O(n)在哪里n.
常数因素也是有利的.我们需要每个数字或分隔符提供一些指令(以及RAM访问); 恒定阶段检查一百万个桶对,在每对上花费类似于另一个少量指令(不需要RAM访问,数据结构非常紧凑).这很闪电.
理论家会说这是作弊.我们假设输入长度没有上限(或者我们根本不能说渐近复杂度),但我们还假设我们可以将总输入长度放到整数变量中.那好吧.
一个更实用的程序员会注意到该算法在字母大小上呈指数级.我们很幸运; 如果我们的单词不是由数字组成,而是除了分隔符之外的任意字符,我们的单词仍然是渐近线性时间算法,但对于任何输入来说它都会非常慢,相比之下,一个天真的算法可以很容易地达到兆字节.一次输入.
创建一个集合数组，每个数字一个集合。
迭代你的数字，并将每个数字放入每个集合中，作为它包含的数字。
迭代所有 10 个集合，并将集合中的每个元素与同一集合中的所有其他元素组合起来。（或所有其他比自身大的元素，如果您不想在结果中出现 (a,b) 和 (b,a) 。
我认为这仍然是 O(n^2) 但可以使用 fork join 方法很好地进行并行化。
更新
刚刚意识到您只想要结果的数量。因此，这将是所有集合的 size * 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...
所以这种方法行不通……我想这对于其他人来说可能是有价值的警告。