arrays - 最快算法的大 O 打印长度为 n 的未排序数组和长度为 m 的排序数组之间的公共(public)元素

Question

我的想法是需要 O(nm) 这是因为
1 2 3 4
4 3 2 1
为了找到共同的元素，您将遍历排序数组和未排序数组(在这种情况下，顶部数组已排序)。最坏的情况下，未排序的数组将是排序的数组，除非颠倒。因此，您将比较 1,4，然后是 1,3，然后是 ... 等等。然后您将比较 2,4，然后是 2,3，等等。 因此，你最终会得到 O(nm)

这是正确的吗？

Answer 1

最快的解决方案是将较小数组的元素放入哈希表中，然后查找较大表中的元素。在实践中，这是 O (max (n, m))。