在N个排序数组中查找没有额外空间的公共元素

Question

给定大小为N的N个数组,并且它们都被排序,如果它不允许你使用额外的空间,那么如何有效地找到它们的公共数据或者用更少的时间复杂度？

例如:

 1. 10 160 200 500 500
 2. 4 150 160 170 500
 3. 2 160 200 202 203
 4. 3 150 155 160 300
 5. 3 150 155 160 301

这是一个面试问题,我发现了一些类似的问题,但它们没有包括输入的额外条件,或者不能使用额外的内存.

我想不出任何低于O(n ^ 2 lg n)复杂度的解决方案.在这种情况下,我更愿意采用最简单的解决方案,这给了我这种复杂性,即:

  not_found_flag = false

  for each element 'v' in row-1
       for each row 'i' in the remaining set
           perform binary search for 'v' in 'i'
           if 'v' not found in row 'i'
                 not_found_flag = true
                 break
       if not not_found_flag 
           print element 'v' as it is one of the common element 

我们可以通过比较每行的最小值和最大值来改进这一点,并根据数量'num'是否可能落在该行的'min_num'和'max_num'之间来决定.

二进制搜索 - > O(log n)用于在n-1行中搜索1个数字:O(nlogn)对第一行中的每个数字进行二进制搜索:O(n2logn)

我选择了第一行,我们可以选择任何行,如果在任何(N-1)行中找不到所选行的元素,那么我们实际上没有共同的数据.

Answer 1

似乎这可以在O(n^2); 即，只查看每个元素一次。请注意，如果一个元素对所有数组都是通用的，那么它必须存在于任何一个数组中。同样出于说明的目的（并且由于您使用了上面的 for 循环），我假设我们可以为每个数组保留一个索引，但稍后我将讨论如何解决这个问题。

让我们A_1通过调用数组A_N，并使用从 1 开始的索引。伪代码：

# Initial index values set to first element of each array
for i = 1 to N:
  x_i = 1 

for x_1 = 1 to N:
  val = A_1[x_1] 
  print_val = true
  for i = 2 to N:
    while A_i[x_i] < val:
      x_i = x_i + 1
    if A_i[x_i] != val:
      print_val = false
  if print_val:
    print val

算法说明。我们使用第一个数组（或任何任意数组）作为参考算法，并并行迭代所有其他数组（有点像合并排序的合并步骤，除了 N 个数组。）参考数组的每个值对所有数组都是通用的，必须存在于所有其他数组中。因此，对于每个其他数组（因为它们已排序），我们增加索引，x_i直到该索引A_i[x_i]处的值至少是我们正在寻找的值（我们不关心较小的值；它们不可能是常见的。）我们可以这样做，因为数组是排序的，因此是单调非递减的。如果所有数组都有这个值，那么我们打印它，否则我们x_1在引用数组中递增并继续。即使我们不打印值，我们也必须这样做。

最后，我们打印了所有数组共有的所有值，而只检查了每个元素一次。

绕过额外的存储要求。有很多方法可以做到这一点，但我认为最简单的方法是检查每个数组的第一个元素并将最大值作为参考数组A_1。如果它们都相同，则打印该值，然后将索引存储x_2 ... x_N为每个数组本身的第一个元素。

Java 实现（为简洁起见，没有额外的 hack），使用您的示例输入：

public static void main(String[] args) {
    int[][] a = {
            { 10, 160, 200, 500, 500, },
            { 4, 150, 160, 170, 500, },
            { 2, 160, 200, 202, 203, },
            { 3, 150, 155, 160, 300 },
            { 3, 150, 155, 160, 301 } };

    int n = a.length;
    int[] x = new int[n];

    for( ; x[0] < n; x[0]++ ) {
        int val = a[0][x[0]]; 
        boolean print = true;
        for( int i = 1; i < n; i++ ) {
            while (a[i][x[i]] < val && x[i] < n-1) x[i]++;              
            if (a[i][x[i]] != val) print = false;               
        }   
        if (print) System.out.println(val);
    }   
}

输出：

160