很难排序算法问题 - O(n)时间 - 时间复杂

Question

由于问题很长,我无法在标题中描述它.

想象一下,我们有2个未排序的整数数组.两个数组长度都是n,并且它们包含介于0 - n ^ 765(最大功率765)之间的整数.

我想比较两个数组,并找出它们是否包含任何相同的整数值与O(n)时间复杂度.

在同一个数组中不可能重复

任何帮助和想法表示赞赏.

Answer 1

你想要的是不可能的.每个元素将以最多log(n ^ 765)位存储,即O(log n).因此,简单地读取两个数组的内容将需要O(n*logn).

如果每个元素的值都有一个常量上限,可以通过将一个数组的元素存储在哈希表中,然后检查另一个数组的元素是否包含在O(n)平均时间内来解决这个问题.它.

编辑:

您可能正在寻找的解决方案是使用基数排序对数据进行排序,之后您可以轻松检查重复元素.您将在基数n中查看您的数字,并对您的数据进行765次传递.每个传递将使用桶排序或计数排序来按单个数字排序(在基数n中).在最坏的情况下,该过程将花费O(n)时间(假设元素大小的上限是恒定的).请注意,我怀疑在实践中有人会选择哈希表.