java - Java，找到两个数组的交集

Question

我已经阅读了其他一些堆栈溢出线程：

public static int[] intersection (int [] x, int numELementsInX, int [] y, int numElementsInY) {

我正在尝试检查两个数组以及它们的元素数量（numElementsInX 和 numElementsInY），并返回一个包含数组 x 和 y 的公共值的新数组。他们的路口。

Example,if x is{1,3,5,7,9}and y is{9,3,9,4} then
intersection(x, 5, y, 4} should return {3, 9} or {9, 3}

我读过我需要使用 LCS 算法。谁能给我一个例子来说明如何做到这一点？数组和数组中的值都在另一种方法中初始化和生成，然后传递给交集。

任何帮助/澄清表示赞赏。

编辑代码

for (int i=0; i<numElementsInX; i++){
    for (int j=0; j<numElementsInY; j++){
        if (x[j]==x[i]) { //how to push to new array?; 
        }
        else{
        }
    }
}

score 54 · Accepted Answer

最简单的解决方案是使用集合，只要您不关心结果中的元素将具有不同的顺序，并且将删除重复项。输入数组array1和array2是Integer[]给定int[]数组的子数组，对应于您打算处理的元素数量：

Set<Integer> s1 = new HashSet<Integer>(Arrays.asList(array1));
Set<Integer> s2 = new HashSet<Integer>(Arrays.asList(array2));
s1.retainAll(s2);

Integer[] result = s1.toArray(new Integer[s1.size()]);

上面将返回一个Integer[]，如果需要，可以很简单地将其内容复制并转换为int[].

score 19 · Accepted Answer

如果您对java-8没问题，那么我能想到的最简单的解决方案是使用流和过滤器。一个实现如下：

public static int[] intersection(int[] a, int[] b) {
    return Arrays.stream(a)
                 .distinct()
                 .filter(x -> Arrays.stream(b).anyMatch(y -> y == x))
                 .toArray();
}

score 3 · Accepted Answer

数组中的重复元素查找交集。

    int [] arr1 = {1,2,2,2,2,2,2,3,6,6,6,6,6,6,};
    int [] arr2 = {7,5,3,6,6,2,2,3,6,6,6,6,6,6,6,6,};

    Arrays.sort(arr1);
    Arrays.sort(arr2);
    ArrayList result = new ArrayList<>();
    int i =0 ;
    int j =0;
    while(i< arr1.length && j<arr2.length){
    if (arr1[i]>arr2[j]){
        j++;

    }else if (arr1[i]<arr2[j]){
        i++;

    }else {
        result.add(arr1[i]);
        i++;
        j++;
    }
    }
    System.out.println(result);

score 2 · Accepted Answer

尝试这个：

public static void main(String[] args) {
    int[] arr1 = new int[]{1, 2, 3, 4, 5};
    int[] arr2 = new int[]{3, 2, 5, 9, 11};
    getIntersection(arr1, arr2);
}

public static Object[] getIntersection(int[] arr1, int[] arr2) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < arr1.length; i++) {
        for (int j = 0; j < arr2.length; j++) {
            if (arr1[i] == arr2[j]) {
                list.add(arr1[i]);
            }
        }
    }
    return list.toArray();
}

score 2 · Accepted Answer

如果您不想使用其他数据结构（例如 Set），那么基本思想是您要遍历其中一个数组的元素，并为每个值查看它是否出现在另一个数组中。你怎么看它是否出现在另一个数组中？遍历另一个数组中的元素，并查看每个元素的值是否等于您要查找的值。如果您上课的目标是学习如何写好 Java，我怀疑您最好自己尝试解决这个问题你写的，所以你可以得到更详细的反馈和正确方向的指示。

score 2 · Accepted Answer

您可以找到两个数组的交集：

T[] result = Arrays.stream(a1)
                   .filter(new HashSet<>(Arrays.asList(a2))::contains)
                   .toArray(T[]::new);

whereT应该可以被引用类型替代，例如 String、Integer 等。

尽管上面看起来像是为每个元素创建了一个新集合，但事实并非如此。而是只创建一个集合实例。

上面的代码等价于：

List<T> list = new ArrayList<>();
HashSet<T> container = new HashSet<>(Arrays.asList(a2));
for (T s : a1) { 
   if (container.contains(s)) list.add(s); 
}
T[] result = list.toArray(new T[0]);

score 1 · Accepted Answer

一般测试

答案提供了几种解决方案，因此我决定找出最有效的一种。

解决方案

HashSet基于Óscar López
基于流的Bilesh Ganguly
Foreach基于Ruchira Gayan Ranaweera
HashMap基于ikarayel

我们有什么

String包含 50% 的公共元素的两个数组。
每个数组中的每个元素都是唯一的，因此没有重复项

测试代码

public static void startTest(String name, Runnable test){
    long start = System.nanoTime();
    test.run();
    long end = System.nanoTime();
    System.out.println(name + ": " + (end - start) / 1000000.  + " ms");
}

随着使用：

startTest("HashMap", () -> intersectHashMap(arr1, arr2));
startTest("HashSet", () -> intersectHashSet(arr1, arr2));
startTest("Foreach", () -> intersectForeach(arr1, arr2));
startTest("Stream ", () -> intersectStream(arr1, arr2));

解决方案代码：

哈希集

public static String[] intersectHashSet(String[] arr1, String[] arr2){
    HashSet<String> set = new HashSet<>(Arrays.asList(arr1));
    set.retainAll(Arrays.asList(arr2));
    return set.toArray(new String[0]);
}

溪流

public static String[] intersectStream(String[] arr1, String[] arr2){
    return Arrays.stream(arr1)
            .distinct()
            .filter(x -> Arrays.asList(arr2).contains(x))
            .toArray(String[]::new);
}

前锋

public static String[] intersectForeach(String[] arr1, String[] arr2){
    ArrayList<String> result = new ArrayList<>();
    for(int i = 0; i < arr1.length; i++){
        for(int r = 0; r < arr2.length; r++){
            if(arr1[i].equals(arr2[r]))
                result.add(arr1[i]);
        }
    }
    return result.toArray(new String[0]);
}

哈希映射

public static String[] intersectHashMap(String[] arr1, String[] arr2){
    HashMap<String, Integer> map = new HashMap<>();
    for (int i = 0; i < arr1.length; i++)
        map.put(arr1[i], 1);

    ArrayList<String> result = new ArrayList<>();
    for(int i = 0; i < arr2.length; i++)
        if(map.containsKey(arr2[i]))
            result.add(arr2[i]);
    return result.toArray(new String[0]);
}

测试过程

让我们看看如果我们给方法一个20元素数组会发生什么：

HashMap: 0.105 ms
HashSet: 0.2185 ms
Foreach: 0.041 ms
Stream : 7.3629 ms

正如我们所见，Foreach方法做得最好。但是Stream方法几乎慢了 180 倍。

让我们继续使用500元素进行测试：

HashMap: 0.7147 ms
HashSet: 4.882 ms
Foreach: 7.8314 ms
Stream : 10.6681 ms

在这种情况下，结果发生了巨大变化。现在最有效的是HashMap方法。

下一个10 000元素测试：

HashMap: 4.875 ms
HashSet: 316.2864 ms
Foreach: 505.6547 ms
Stream : 292.6572 ms

最快的还是HashMap方法。而且Foreach方法变得相当缓慢。

结果

如果有 < 50 个元素，那么最好使用该Foreach方法。他在这一类别中的速度非常出色。

在这种情况下，最好的顶部将如下所示：

Foreach
HashMap
HashSet
Stream- 最好不要在这种情况下使用

但是，如果您需要处理大数据，那么最好的选择是使用HashMap基于方法。

所以最好的顶部看起来像这样：

HashMap
HashSet
Stream
Foreach

score 0 · Accepted Answer

使用哈希图查找交叉点包括重复项。

输出：1 2 2 15 9 7 12

public static void main(String[] args) {
    int[] arr1 = {1, 2, 2, 1, 5, 9, 15, 9, 7, 7, 12};
    int[] arr2 = {1, 2, 2, 3, 4, 15, 9, 7, 12, 14};
    printIntersect(arr1, arr2);
}

private static void printIntersect(int[] arr1, int[] arr2) {
    Map<Integer, Integer> map = new HashMap<>();
    //put first array to map
    for (int i = 0; i < arr1.length; i++) {
        if (!map.containsKey(arr1[i])) {
            map.put(arr1[i], 1);
        } else {
            map.put(arr1[i], map.get(arr1[i]) + 1);
        }
    }

    //check all value in array two
    for (int i = 0; i < arr2.length; i++) {
        //if exist and value>1  then decrement value
        //if value is 1 remove from map
        if (map.containsKey(arr2[i])) {
            System.out.print(arr2[i] + " ");
            if (map.get(arr2[i]) > 1) {
                map.put(arr2[i], map.get(arr2[i]) - 1);
            } else {
                map.remove(arr2[i]);
            }
        }
    }
}

score 0 · Accepted Answer

原始迭代器：比 HashSet 快 6 倍

在10,000,000 个随机元素的排序数组上进行测试，值在 0 到 200,000,000 之间。在具有 4GB 堆空间的 10 处理器 i9 上进行了测试。两个数组的排序时间为 1.9 秒。

结果：

原始（） - 1.1 秒

public static int[] primitive(int[] a1, int[] a2) {
    List<Integer> list = new LinkedList<>();
    OfInt it1 = Arrays.stream(a1).iterator();
    OfInt it2 = Arrays.stream(a2).iterator();
    int i1 = it1.next();
    int i2 = it2.next();
    do {
      if (i1==i2) {
        list.add(i1);
         i1 = it1.next();
      }
      if (i1 < i2) i1 = it1.next();
      if (i2 < i1) i2 = it2.next();
    } while(it1.hasNext() && it2.hasNext());
    if (i1==i2) list.add(i1);
    return list.stream().mapToInt(Integer::intValue).toArray();
  }

boxed() - 6.8 秒

  public static int[] boxed(int[] a1, int[] a2) {
    return Arrays.stream(a1)
                   .filter(new HashSet<>(Arrays.stream(a2).boxed()
                         .collect(Collectors.toList()))::contains)
                   .toArray();
  }

score 0 · Accepted Answer

如何在 Java 中找到 3 个未排序数组的交集：-

我使用了核心 Java 方法，使用 for 循环和使用 Arrays.copyOf 来实现这一点。

public class Intersection {
    public void intersection3Arrays(int ar1[], int ar2[], int ar3[]) {
            Arrays. sort(ar1);
            Arrays. sort(ar2);
            Arrays. sort(ar3);

            int ar1Len = ar1.length;
            int ar2Len = ar2.length;
            int ar3Len = ar3.length;

            int larArray = ar3Len > (ar1Len > ar2Len ? ar1Len : ar2Len) ? ar3Len : ((ar1Len > ar2Len) ? ar1Len : ar2Len);
            System.out.println("The largest array is " +larArray);
            int[] inputArray1 = Arrays.copyOf(ar1, larArray);
            int[] inputArray2 = Arrays.copyOf(ar2, larArray);
            int[] inputArray3 = Arrays.copyOf(ar3, larArray);

            Integer[] inputArray11 = new Integer[inputArray1.length];
            Integer[] inputArray22 = new Integer[inputArray2.length];
            Integer[] inputArray33 = new Integer[inputArray3.length];

            for (int i = 0; i < inputArray11.length; i++) {
                if (inputArray11[i] == null){
                    inputArray1[i] = 0;
                }
            }
            for (int i = 0; i < inputArray22.length; i++) {
                if (inputArray22[i] == null){
                    inputArray1[i] = 0;
                }
            }
            for (int i = 0; i < inputArray33.length; i++) {
                if (inputArray33[i] == null){
                    inputArray1[i] = 0;
                }
            }

            for (int i = 0; i < inputArray11.length; i++)
                for (int j = 0; j < inputArray22.length; j++)
                    for (int k = 0; k < inputArray33.length; j++)
                    if (inputArray11[i] == inputArray22[j] && inputArray11[i] == inputArray33[k]) {
                        System.out.print(inputArray11[i]+" ");
                    }
        } 
    public static void main(String[] args) {
        Intersection3Arrays arrays = new Intersection3Arrays();
        int ar1[] = { 1, 2, 5, 10, 20, 40, 80 };
        int ar2[] = { 80, 100, 6, 2, 7, 20 };
        int ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}; 
        arrays.intersection3Arrays(ar1, ar2, ar3);
    }
}

score 0 · Accepted Answer

我希望这个例子是简单的 one.pass 两个数组，你肯定会得到数组的 INTERSECTION 而没有重复项。

private static int[] findInterserctorOfTwoArray(int[] array1, int[] array2) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int element : array1) {
            for (int element2 : array2) {
                if(element==element2) {
                    map.put(element, element);
                }
            }
        }
        int[] newArray=new int[map.size()];
        int con=0;
        for(Map.Entry<Integer, Integer> lst:map.entrySet()) {
            newArray[con]=lst.getValue();
            con++;
        }
        return newArray;
    }

score 0 · Accepted Answer

针对仅使用一个循环的排序数组进行了优化。

    int a1[]=new int[] {1,2,3,5,7,8};
    int a2[]=new int [] {1,5,6,7,8,9};
 // sort both the array
     Arrays.sort(a1);
     Arrays.sort(a2);
     // get the length of both the array
    int n1=a1.length;
    int n2=a2.length;

 //create a new array to store the intersection
   int a3[]=new int[n1];
    
     //run the loop and find the intersection
    int i=0,j=0,k=0;
    while(i<n1&& j<n2) {
        if(a1[i]<a2[j]) {
         // a1 element at i are smaller than a2 element at j so increment  i
            i++;
        }else if(a1[i]>a2[j]) {
         // a2 element at i are smaller than a2 element at j so increment  j
            
            j++;
        }else {
             // intersection element store the value and increment i, j, k    to find the next element
            a3[k]=a1[i];
            i++;
            j++;
            k++;
        }
    }
    
    
    for(int l=0;l<a3.length;l++) {
        System.out.println(a3[l]);
    }

score 0 · Accepted Answer

如果你想在 python 中实现它，这是你可以找到交集的一种方法。

#find intersection
def find_intersec(list_a, list_b): 
    return set(list_a).intersection(list_b) 

#since lists are kind of like arrays in python we use two lists
list_a = [ 4, 9, 1, 17, 11, 26, 28, 10,28, 26, 66, 91] 
list_b = [9, 9, 74, 21, 45, 11, 63,10] 
print(find_intersec(list_a, list_b))

score 0 · Accepted Answer

如果数组已排序

    int a1[]=new int[] {1,2,3,5,7,8};
    int a2[]=new int [] {1,5,6,7,8,9};

     // get the length of both the array
    int n1=a1.length;
    int n2=a2.length;

 //create a new array to store the intersection
   int a3[]=new int[n1];

     //run the loop and find the intersection
    int i=0,j=0,k=0;
    while(i<n1&& j<n2) {
        if(a1[i]<a2[j]) {
         // a1 element at i are smaller than a2 element at j so increment  i
            i++;
        }else if(a1[i]>a2[j]) {
         // a2 element at i are smaller than a2 element at j so increment  j

            j++;
        }else {
             // intersection element store the value and increment i, j, k    to find the next element
            a3[k]=a1[i];
            i++;
            j++;
            k++;
        }
    }


    for(int l=0;l<a3.length;l++) {
        System.out.println(a3[l]);
    }