7

我今天在一次采访中被问到一个算法问题，我很想得到 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 Arrays 虽然我认为这仍然存在。

我的问题是，考虑到时间复杂度，有没有更好的方法来解决这个问题？

4

9 回答 9

9

Treat as 3 queues. While values are different, "remove" (by incrementing the array index) the smallest. When they match, "remove" (and record) the matches.

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++;
    }
}

Easily generalized to N arrays, though with N large you'd want to optimize the compares somehow (NPE's "heap").

于 2013-03-25T15:03:49.783 回答
5

我认为这可以通过对 N 数组和 N 元素min-heap进行一次并行迭代来解决。在堆中，您将保留 N 个输入数组中的每一个的当前元素。

这个想法是，在每个步骤中，您都将沿着其元素位于堆顶部（即最小）的数组前进。

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

如果每个数组包含 M 个元素，则最坏情况下的时间复杂度将是O(M*N*log(N))并且需要O(N)内存。

于 2013-03-25T15:08:29.800 回答
2

这可以O(M * N)用 M 作为数组的长度来解决。

让我们看看会发生什么N = 2，这将是一个排序列表交集问题，它有一个经典的类似合并的解决方案O(l1 + l2)及时运行。（l1 = 第一个数组的长度，l2 = 第二个数组的长度）。（了解有关合并算法的更多信息。）

现在，让我们在归纳问题中重新迭代算法 N 次。（例如，第 i 次我们将得到第 i 个数组，以及上一步的交集结果）。这将产生一个整体O(M * N)算法。

您还可以观察到，这个最坏情况的上限是最好的，因为任何有效算法都必须考虑所有数字。因此，不可能建立具有更严格上限的确定性算法。

于 2013-03-25T15:20:27.020 回答
2

尝试

public static Set<Integer> commonNumbers(int[] arr1, int[] arr2, int[] arr3) {
    Set<Integer> s1 = createSet(arr1);
    Set<Integer> s2 = createSet(arr2);
    Set<Integer> s3 = createSet(arr3);
    s1.retainAll(s2);
    s1.retainAll(s3);
    return s1;
}

private static Set<Integer> createSet(int[] arr) {
    Set<Integer> s = new HashSet<Integer>();
    for (int e : arr) {
        s.add(e);
    }
    return s;
}
于 2013-03-25T15:14:27.167 回答
2

这就是我在算法课上学习的方式。不确定它是否“更好”，但它使用更少的内存和更少的开销，因为它直接遍历数组而不是先构建地图。

public static List<Integer> commonNumbers(int[] arr1, int[] arr2, int[] arr3, ... , int[] arrN) {
    List<Integer>toReturn = new LinkedList<Integer>();

    int len = arr1.length;
    int j = 0, k = 0, ... , counterN = 0;
    for (int i = 0; i < len; i++) {
        while (arr2[j] < arr1[i] && j < len) j++;
        while (arr3[k] < arr1[i] && k < len) k++;
        ...
        while (arrN[counterN] < arr1[i] && counterN < len) counterN++;
        if (arr1[i] == arr2[j] && arr2[j] == arr3[k] && ... && arr1[i] == arrN[counterN]) {
            toReturn.add(arr1[i]);
        }
    }

    return toReturn;
}
于 2013-03-25T15:14:28.950 回答
1

好的 - 这里可能有点天真，但我认为线索是数组是按升序排列的。我的 java 生锈了，但这里有一些伪代码。我还没有测试过它，所以它可能并不完美，但它应该是一种快速的方法：

I = 1
J = 1
K = 1

While I <= Array1Count and J <= Array2Count and K <= Array3Count

   If Array1(I) = Array2(J)
      If Array1(I) = Array3(K)
         === Found Match
         I++
         J++
         K++
      else
         if Array1(I) < Array3(K)
            I++
         end if
      end if
   else
      If Array1(I) < Array2(J)
         I++
      else
         if Array2(J) < Array3(K)
            J++
         else
            K++
         end if
      end if
   end if
Wend

这是 Option Base 1 - 您必须重新编码才能执行 option base 0（就像 java 和其他语言一样）

于 2013-03-25T15:14:11.397 回答
0

您的解决方案是可以接受的，但它使用 NxM 空间。您可以使用 O(N) 空间（其中 N 是数组的数量）或 O(1) 空间来执行此操作。

解决方案 #1（由 Luigi Mendoza 提供）

假设有许多小数组（M << N），这可能很有用，导致 O(M*N*Log M) 时间和恒定空间（不包括输出列表）。

解决方案#2

按升序扫描数组，维护一个大小为 N 的最小堆，其中包含数组的最新访问值（和索引）。每当堆包含相同值的 N 个副本时，将该值添加到输出集合中。否则，删除最小值并使用相应的列表前进。

这个解的时间复杂度是 O(M*N*Log N)

于 2013-03-25T15:15:09.543 回答
0

我认为另一种方法是做类似于我们在 Mergesort 中所做的事情：同时遍历所有数组，得到相同的数字。这将利用数组按排序顺序的事实，并且除了输出数组之外不会使用额外的空间。如果您只需要打印常见的数字，则不会使用额外的空间。

public static List<Integer> commonNumbers(int[] arrA, int[] arrB, int[] arrC) {
   int[] idx = {0, 0, 0};

   while (idxA<arrA.length && idxB<arrB.length && idxC<arrC.length) {
      if ( arrA[idx[0]]==arrB[idx[1]] && arrB[idx[1]]==arrC[idx[2]] ) {
          // Same number
          System.out.print("Common number %d\n", arrA[idx[0]]);
          for (int i=0;i<3;i++)
              idx[i]++;
      } else {
          // Increase the index of the lowest number
          int idxLowest = 0; int nLowest = arrA[idx[0]];
          if (arrB[idx[1]] < nLowest) {
             idxLowest = 1;
             nLowest = arrB[idx[1]];
          }
          if (arrC[idx[2]] < nLowest) {
             idxLowest = 2;
          }
          idx[idxLowest]++;
      }
   }
}

为了使这更通用，您可能需要采用整数数组的数组，这将使您的代码更漂亮。数组索引必须存储在数组中，否则很难编写“递增指向最小数字的索引”代码。

于 2013-03-25T15:14:21.827 回答
0 
public static List<Integer> getCommon(List<List<Integer>> list){
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    int c=0;
    for (List<Integer> is : list) {
        c++;
        for (int i : is) {
            if(map.containsKey(i)){
                map.put(i, map.get(i)+1);
            }else{
                map.put(i, 1);
            }
        }
    }
     List<Integer>toReturn = new LinkedList<Integer>();
    for(int key:map.keySet())
    {
        int count = map.get(key);
        if(count==c)toReturn.add(key);
    }
    return toReturn;
}
于 2013-03-25T17:21:24.110 回答