java - 对于 N 个大小相等且整数按升序排列的数组，如何选择数组共有的数字？

Question

我今天在接受采访时被问到一个算法问题，我很想听取 SO 成员的意见。问题如下；

给定大小相等且整数按升序排列的 N 个数组，您将如何选择所有 N 个数组共有的数字。

起初我的想法是迭代从第一个数组开始的元素，逐渐向下到其余数组。但如果我是对的，那将导致 N 次 N 次迭代。所以我想出了一个解决方案，通过将元素作为键并将值作为计数器来将计数添加到 map 中。这样我相信时间复杂度仅为 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 的“堆”)。