对于具有整数升序的N个大小相等的数组,如何选择数组常用的数字？

Question

我今天在一次采访中被问到一个算法问题,我很想得到SO成员的同意.问题如下;

给定大小相等的N个数组,按升序排列整数,如何选择所有N个数组共有的数字.

起初我的想法是迭代从第一个数组滴流到其余数组的元素.但如果我是正确的话,那将导致N次幂N次迭代.那么我想出了一个解决方案,通过将元素保持为键,将值作为计数器,将计数添加到地图中.这种方式我认为时间复杂度只是N.以下是我用Java实现的方法

public static void main(String[] args) {

    int[] arr1 = { 1, 4, 6, 8,11,15 };
    int[] arr2 = { 3, 4, 6, 9, 10,16 };
    int[] arr3 = { 1, 4, 6, 13,15,16 };
    System.out.println(commonNumbers(arr1, arr2, arr3));
}

public static List<Integer> commonNumbers(int[] arr1, int[] arr2, int[] arr3) {
    Map<Integer, Integer>countMap = new HashMap<Integer, Integer>();

    for(int element:arr1)
    {
        countMap.put(element, 1);
    }

    for(int element:arr2)
    {
        if(countMap.containsKey(element))
        {
            countMap.put(element,countMap.get(element)+1);
        }
    }

    for(int element:arr3)
    {
        if(countMap.containsKey(element))
        {
            countMap.put(element,countMap.get(element)+1);
        }
    }

    List<Integer>toReturn = new LinkedList<Integer>();

    for(int key:countMap.keySet())
    {
        int count = countMap.get(key);
        if(count==3)toReturn.add(key);
    }

    return toReturn;
}

我只是为三个数组做了这个,看看它是如何工作的.问题谈论N阵列虽然我认为这仍然有效.

我的问题是,是否有更好的方法来解决这个问题时间复杂性？

Answer 1

视为3个队列.虽然值不同,但"删除"(通过递增数组索引)最小.当他们匹配时,"删除"(并记录)比赛.

int i1 = 0;
int i2 = 0;
int i3 = 0;

while (i1 < array1.size && i2 < array2.size && i3 < array3.size) {
    int next1 = array1[i1];
    int next2 = array2[i2];
    int next3 = array3[i3];

    if (next1 == next2 && next1 == next3) {
        recordMatch(next1);
        i1++;
        i2++;
        i3++;
    }
    else if (next1 < next2 && next1 < next3) {
        i1++;
    }
    else if (next2 < next1 && next2 < next3) {
        i2++;
    }
    else {
        i3++;
    }
}

很容易推广到N个数组,虽然N大,你想要以某种方式优化比较(NPE的"堆").

Answer 2

我认为这可以通过N个阵列上的单个并行迭代和N个元素的最小堆来解决.在堆中,您将保留N个输入数组中的每一个的当前元素.

我们的想法是,在每个步骤中,您将沿着数组前进,其元素位于堆的顶部(即最小).

您需要能够检测堆何时完全由相同的值组成.只要您跟踪已添加到堆中的最大元素,就可以在恒定时间内完成此操作.

如果每个数组包含M个元素,那么最坏情况下的时间复杂度将是O(M*N*log(N))需要O(N)内存的.