(算法)查找两个未排序的数组在O(n)时间内是否有任何公共元素而没有排序？

Question

我们有两个未排序的数组,每个数组的长度为n.这些数组包含0-n ¹⁰⁰范围内的随机整数.如何找出这两个数组在O(n)/线性时间内是否有任何共同元素？不允许排序.

Answer 1

Hashtable会救你.真的,它就像算法的瑞士刀.
只需将第一个数组中的所有值放入其中,然后检查第二个数组中是否存在任何值.

@Neil:搜索通常是O(1),构建是O(n). (4认同)
虽然这在实践中是一个很好的方法,但它没有达到O(n)*最差情况*的性能.首先,因为哈希表查找在最坏的情况下是O(n)(错误的哈希函数,并且对于每个哈希函数,存在具有许多哈希冲突的输入),并且第二,因为您隐含地假设哈希函数可以在恒定时间内计算即使用于保存数字的位数不是恒定的. (4认同)
使用哈希表是O(nlog n). (2认同)

Answer 2

您尚未定义计算模型.假设你只能在O(1)时间内读取O(1)位(其他任何东西都是一个相当奇特的计算模型),就没有算法可以解决O(n)最坏情况时间复杂度的问题.

证明草图:输入中的每个数字都取O(log(n ^ 100))= O(100 log n)= O(log n)位.因此整个输入为O(n log n)位,在O(n)时间内无法读取.因此,任何O(n)算法都不能读取整个输入,因此如果这些位重要则不作出反应.

-1:这正在打败问题的精神.此外,Word RAM模型并不是那种奇特.实际上,大多数算法时间复杂度分析隐含地使用了当未指定时:O(1)时间数组访问,O(1)添加两个适合寄存器的整数等. (3认同)