Abh*_*yap -3 arrays algorithm intersection time-complexity
我知道这类问题已经在社区中被重复提出,但我的问题与其他问题没什么不同.
我今天面对一家知名公司的采访.他们问我两个技术问题,其中一个问题是......
我已经给出了两个未分类的长度数组,他们要求我找到数组的常用元素,但使用时间复杂度为O(n)的算法.
没有额外的语言相关支持.
我向他们展示了一个时间复杂度为O(n*log(n))的算法,但他们并不满意.我只想知道是否存在任何此类算法.
您可以使用散列映射来存储第一个数组的所有元素(以及它们的计数以处理重复元素的情况).
然后遍历第二个数组并检查它们是否存在于hashmap中.理想情况下,时间复杂度O(2n).因为放置元素并从中检索是在O(1)时间内.
你实现了O(n)的时间复杂度,但你space complexity也变成了O(n).