以线性时间复杂度查找两个数组中的公共元素

Question

我知道这类问题已在社区中反复问过，但我的问题与其他问题没什么不同。

我今天面对一家知名公司的采访。他们问了我两个技术问题，其中一个是...

我给了两个长度未排序的数组，说n他们要求我找到数组的公共元素，但是算法的时间复杂度为O（n）。

没有额外的语言相关支持。

我向他们展示了一种算法，其时间复杂度为O（n * log（n）），但他们并不满意。我只想知道如果存在任何这种算法。

Answer 1

您可以使用哈希图存储第一个数组的所有元素（以及它们的计数以处理重复元素的情况）。

然后遍历第二个数组，并检查它们是否在哈希图中。理想情况下，时间复杂度为O(2n)。由于放置元素并从中进行检索的时间为O（1）。

您获得的时间复杂度为O（n），但您的space complexity也变为O（n）。

Answer 2

您可以使用HashSet（在C ++中为unordered_multiset）来存储第一个数组的元素，然后遍历第二个数组，找到HashTable中存在的元素。由于访问元素平均具有恒定的时间复杂度，因此该算法将在O（n）中运行。

Answer 3

借助于注释和其他答案，我得出的结论是，如果不使用C ++中的HashMap或Python中的set]，就不可能在O（n）中做到这一点。这实际上是语言的支持，也增加了空间的复杂性。]

所以，这是python中的解决方案：

list1 = [4,2,5,7,1]
list2 = [8,2,4,1,6]

ans =  list(set(list1) & set(list2))
print 'Common Elements: ',ans

>>> Common Elements:  [1, 2, 4]

Answer 4

public static void commonElementsInTwoArrays() {
        int[] arr1= {4,6,8,9};
        int[] arr2= {4,6,8,7};
        int i=0,j=0;

        while(i<arr1.length & j<arr2.length) {
            if(arr1[i]==arr2[j]) {
                System.out.println(arr1[i]);
                i++;
                j++;
            }else if(arr1[i]<arr2[j]) {
                i++;
            }else {
                j++;
            }
        }
    }