在两个不同大小的数组中查找公共元素

Question

我有一个问题是在两个数组中找到不同大小的公共元素.

Take,A1Size of size n和Array A2of size m,andm != n

到目前为止,我已经尝试逐个迭代列表并将元素复制到另一个列表.如果元素已经包含标记,但我知道它不是一个好的解决方案.

Answer 1

对数组进行排序.然后用两个指针迭代它们,总是推进指向较小值的指针.当他们指向相等的值时,您就有一个共同的价值.这将是O(n + m),其中n和m是两个列表的大小.它就像合并排序中的合并,但是当指向的值相等时,您只生成输出.

def common_elements(a, b):
  a.sort()
  b.sort()
  i, j = 0, 0
  common = []
  while i < len(a) and j < len(b):
    if a[i] == b[j]:
      common.append(a[i])
      i += 1
      j += 1
    elif a[i] < b[j]:
      i += 1
    else:
      j += 1
  return common

print 'Common values:', ', '.join(map(str, common_elements([1, 2, 4, 8], [1, 4, 9])))

输出

Common values: 1, 4

如果元素不具有可比性,则将一个列表中的元素抛出到散列映射中,并根据散列映射检查第二个列表中的元素.

Answer 2

如果你想提高效率,我会将较小的数组转换为一个hashset,然后迭代较大的数组并检查当前元素是否包含在hashset中.与排序数组相比,散列函数是有效的.排序数组很昂贵.

这是我的示例代码

import java.util.*;
public class CountTest {     
    public static void main(String... args) {        
        Integer[] array1 = {9, 4, 6, 2, 10, 10};
        Integer[] array2 = {14, 3, 6, 9, 10, 15, 17, 9};                    
        Set hashSet = new HashSet(Arrays.asList(array1)); 
        Set commonElements = new HashSet();        
        for (int i = 0; i < array2.length; i++) {
            if (hashSet.contains(array2[i])) {
                commonElements.add(array2[i]);
            }
        }
        System.out.println("Common elements " + commonElements);
    }    
}

输出:

共同要素[6,9,10]