不需要额外空间，在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)行中没有找到该行选择的任何一个元素，则实际上我们没有共同的数据。

- user1071840

---

你需要“一些”额外的空间来存储（可能的）共同元素... - Mitch Wheat

@MitchWheat。请看上面的伪代码。如果我们只打印共同元素，我们真的需要额外的存储空间吗？ - user1071840

你真的通过二分查找节省了时间吗？因为你需要找到所有的共同元素，为什么不直接扫描排序后的数组，在O(n)的时间内完成呢？ - smk

@smk。有“N”个不同的数组，每个数组都是独立排序的。我已经在问题中编辑了示例。我们无法通过扫描“N”个数组以O（n）找到公共元素。它更像是一个NXN的方阵，其中每行都是单独排序的。 - user1071840

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

- Andrew Mao

Answer 2

这是一个使用Python实现的解决方案，时间复杂度为O(n^2)，不需要额外的空间，但会改变原有列表：

def find_common(lists):
    num_lists = len(lists)
    first_list = lists[0]
    for j in first_list[::-1]:
        common_found = True
        for i in range(1,num_lists):
            curr_list = lists[i]
            while curr_list[len(curr_list)-1] > j:
                curr_list.pop()
            if curr_list[len(curr_list)-1] != j:
                common_found = False
                break
        if common_found:
            return j

- user2214455

Answer 3

这是Java的实现。

public static Integer[] commonElementsInNSortedArrays(int[][] arrays) {
    int baseIndex = 0, currentIndex = 0, totalMatchFound= 0;
    int[] indices = new int[arrays.length - 1];
    boolean smallestArrayTraversed = false;
    List<Integer> result = new ArrayList<Integer>();
    while (!smallestArrayTraversed && baseIndex < arrays[0].length) {
        totalMatchFound = 0;
        for (int array = 1; array < arrays.length; array++) {
            currentIndex = indices[array - 1];
            while (currentIndex < arrays[array].length && arrays[array][currentIndex] < arrays[0][baseIndex]) {
                currentIndex ++;                    
            }

            if (currentIndex < arrays[array].length) {
                if (arrays[array][currentIndex] == arrays[0][baseIndex]) {
                    totalMatchFound++;
                }
            } else {
                smallestArrayTraversed = true;
            }
            indices[array - 1] = currentIndex;
        }
        if (totalMatchFound == arrays.length - 1) {
            result.add(arrays[0][baseIndex]);
        }
        baseIndex++;
    }

    return result.toArray(new Integer[0]);
}

这是单元测试。

@Test
public void commonElementsInNSortedArrayTest() {
    int arr[][] = { {1, 5, 10, 20, 40, 80},
                    {6, 7, 20, 80, 100},
                    {3, 4, 15, 20, 30, 70, 80, 120}
                   };

    Integer result[] = ArrayUtils.commonElementsInNSortedArrays(arr);
    assertThat(result, equalTo(new Integer[]{20, 80}));

    arr = new int[][]{
            {23, 34, 67, 89, 123, 566, 1000},
            {11, 22, 23, 24,33, 37, 185, 566, 987, 1223, 1234},
            {23, 43, 67, 98, 566, 678},
            {1, 4, 5, 23, 34, 76, 87, 132, 566, 665},
            {1, 2, 3, 23, 24, 344, 566}
          };

    result = ArrayUtils.commonElementsInNSortedArrays(arr);
    assertThat(result, equalTo(new Integer[]{23, 566}));
}

- craftsmannadeem

Answer 4

一个O(n^2)（Python）版本，不使用额外的存储空间，但修改原始数组。允许存储共同元素而不打印它们：

data = [
    [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],
]

for k in xrange(len(data)-1):
    A, B = data[k], data[k+1]
    i, j, x = 0, 0, None

    while i<len(A) or j<len(B):
        while i<len(A) and (j>=len(B) or A[i] < B[j]):
            A[i] = x
            i += 1

        while j<len(B) and (i>=len(A) or B[j] < A[i]):
            B[j] = x
            j += 1

        if i<len(A) and j<len(B):
            x = A[i]
            i += 1
            j += 1

print data[-1]

我所做的基本上是获取数据中的每个数组并逐个比较其相邻的元素，删除不相同的元素。

- Juan Lopes

Answer 5

这个Swift解决方案复制了原始内容，但可以修改为采用inout参数，以便不占用额外的空间。我将它保留为一个副本，因为我认为最好不要修改原始内容，因为这会删除元素。通过保留索引可以不删除元素，但这个算法删除元素来跟踪位置。这是一种功能性方法，可能不是特别高效，但有效。由于是功能性方法，所以需要的条件逻辑较少。我发布它是因为我觉得它可能是一个不同的方法，可能对其他人很有趣，并且也许其他人可以想出更有效的方法。

func findCommonInSortedArrays(arr: [[Int]]) -> [Int] {
    var copy = arr
    var result: [Int] = []

    while (true) {

        // get first elements
        let m = copy.indices.compactMap { copy[$0].first }

        // find max value of those elements.
        let mm = m.reduce (0) { max($0, $1) }

        // find the value in other arrays or nil
        let ii = copy.indices.map { copy[$0].firstIndex { $0 == mm } }

        // if nil present in of one of the arrays found, return result
        if (ii.map { $0 }).count != (ii.compactMap { $0 }.count) { return result }

        // remove elements that don't match target value.
        copy.indices.map { copy[$0].removeFirst( ii[$0] ?? 0 ) }

        // add to list of matching values.
        result += [mm]

        // remove the matched element from all arrays
        copy.indices.forEach { copy[$0].removeFirst() }
    }
}

findCommonInSortedArrays(arr: [[9, 10, 12, 13, 14, 29],
                         [3, 5, 9, 10, 13, 14],
                         [3, 9, 10, 14]]
)

findCommonInSortedArrays(arr: [[],
                         [],
                         []]
)

findCommonInSortedArrays(arr: [[9, 10, 12, 13, 14, 29],
                         [3, 5, 9, 10, 13, 14],
                         [3, 9, 10, 14],
                         [9, 10, 29]]
)

findCommonInSortedArrays(arr: [[9, 10, 12, 13, 14, 29],
                               [3, 5, 9, 10, 13, 14],
                               [3, 9, 10, 14],
                               [9, 10, 29]]
)

- possen