如何将两个数组之间的交集作为新数组？

Question

在各种情况下我多次遇到这个问题.虽然我对C或Java感到满意,但它对所有编程语言都是通用的.

让我们考虑两个数组(或集合):

char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};

如何将两个数组之间的公共元素作为新数组？在这种情况下,阵列A和B的交点是char[] c = {'c', 'd'}.

我想避免在另一个数组内重复迭代一个数组,这将增加执行时间(A长度为B的长度),这对于大型数组来说太多了.

有没有什么办法可以在每个数组中单独传递以获得公共元素？

Answer 1

foreach element e in array A
    insert e into hash table H

foreach element e in array B
    if H contains e 
        print e

该算法O(N)在时间和O(N)空间上.

为了避免额外的空间,您可以使用基于排序的方法.

Answer 2

效率的下限是O(n) - 你至少需要读取所有元素.然后有几个apporaches:

愚蠢最简单的方法

从数组2中的第一个数组中搜索每个元素.时间复杂度O(n ^ 2).

排序方法

您只需要对数组1进行排序,然后使用二进制搜索从数组2中搜索元素.时间复杂度:排序O(nlogn),搜索O(n*logn)= O(nlogn),总O(nlogn).

哈希方法

从数组一个元素创建一个哈希表.从哈希表中的第二个表中搜索元素.时间复杂度取决于散列函数.您可以在最佳情况下为搜索实现O(1)(所有元素将具有不同的哈希值),但在最坏的情况下为O(n)(所有元素将具有相同的哈希值).总时间复杂度:O(n ^ x),其中x是散列函数效率的因子(在1和2之间).

一些散列函数可以保证构建一个没有冲突的表.但是建筑物不再需要每个元素严格的O(1)时间.在大多数情况下它将是O(1),但如果表已满或遇到碰撞,则表需要重新进行 - 花费O(n)时间.这种情况不常发生,比清洁添加频繁得多.因此,AMORTIZED时间复杂度为O(1).只要大多数添加花费O(1)时间,我们就不关心花费O(n)时间的一些添加.

但即便如此,在极端情况下,每次插入时都必须重新进行表格,因此严格的时间复杂度为O(n ^ 2)

Answer 3

我知道某些语言中有一些方法可以完全满足您的需求,您是否考虑过查看其中一些实现？

PHP - array_intersect()

$array1 = array("a" => "green", "red", "blue");
$array2 = array("b" => "green", "yellow", "red");
$result = array_intersect($array1, $array2);
print_r($result);

>> green
   red

Java - List.retainAll

Collection listOne = new ArrayList(Arrays.asList("milan","dingo", "elpha", "hafil", "meat", "iga", "neeta.peeta"));
Collection listTwo = new ArrayList(Arrays.asList("hafil", "iga", "binga", "mike", "dingo"));

listOne.retainAll( listTwo );
System.out.println( listOne );

>> dingo, hafil, iga

Answer 4

因为这对我来说就像一个字符串算法,我会假设它不可能排序这个序列(因此字符串)然后你可以使用最长公共序列算法(LCS)

假设输入大小是常数,则问题的复杂度为O(nxm),(两个输入的长度)

Answer 5

    public static void main(String[] args) {
        char[] a = {'a', 'b', 'c', 'd'};
        char[] b = {'c', 'd', 'e', 'f'};
        System.out.println(intersect(a, b));
    }

    private static Set<Character> intersect(char[] a, char[] b) {
        Set<Character> aSet = new HashSet<Character>();
        Set<Character> intersection = new HashSet<Character>();
        for (char c : a) {
            aSet.add(c);
        }
        for (char c : b) {
            if (aSet.contains(c)) {
                intersection.add(c);
            }
        }
        return intersection;
    }