最快算法的大 O 打印长度为 n 的未排序数组和长度为 m 的排序数组之间的公共元素
Big O of the fastest algo to print the common elements between an unsorted array of length n and sorted array of length m
我的想法是需要 O(nm)
这是因为
1 2 3 4
4 3 2 1
为了找到共同的元素，您将遍历排序数组和未排序数组（在这种情况下，顶部数组已排序）。最坏的情况下，未排序的数组将是排序的数组，除非颠倒。因此，您将比较 1,4，然后是 1,3，然后是 ... 等等。然后您将比较 2,4，然后是 2,3，等等。
因此，你最终会得到 O(nm)
这是正确的吗？
感谢 j_random_hacker、
应该是O(log(n)*m)
您可以使用二分查找从已排序数组中的未排序数组中查找每个项目，这是 log(n) 时间。对于未排序数组中的每一项，这应该是 O(log(n)*m) 时间。
最快的解决方案是将较小数组的元素放入散列 table，然后查找较大数组 table 的元素。在实践中，这是 O (max (n, m))。
我的想法是需要 O(nm)
这是因为
1 2 3 4
4 3 2 1
为了找到共同的元素，您将遍历排序数组和未排序数组（在这种情况下，顶部数组已排序）。最坏的情况下，未排序的数组将是排序的数组，除非颠倒。因此，您将比较 1,4，然后是 1,3，然后是 ... 等等。然后您将比较 2,4，然后是 2,3，等等。
因此，你最终会得到 O(nm)
这是正确的吗？
感谢 j_random_hacker、
应该是O(log(n)*m)
您可以使用二分查找从已排序数组中的未排序数组中查找每个项目，这是 log(n) 时间。对于未排序数组中的每一项，这应该是 O(log(n)*m) 时间。
最快的解决方案是将较小数组的元素放入散列 table，然后查找较大数组 table 的元素。在实践中，这是 O (max (n, m))。