Java, найти пересечение двух массивов

Question

я уже прочитал несколько других переполнение стека потоков на это:

to find the intersection of two multisets in java

How do I get the intersection between two arrays as a new array?

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. Может ли кто-нибудь дать мне пример, как это сделать? И массив, и значения в массиве инициализируются и генерируются другим методом, а затем передаются в пересечение.

Любая помощь/разъяснение оцениваются.

EDIT CODE

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{ 
     } 
    } 
} 

Answer 1

Самым простым решением было бы использовать наборы, до тех пор, пока вы не заботитесь о том, что элементы в результате будет иметь различный порядок, и что дубликаты будут удалены , Входные массивы 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[].

Answer 2

Если вы не хотите использовать другие структуры данных, такие как набор, то основная идея заключается в том, что вы хотите итерации по элементам одного из массивов и для каждого значения посмотреть, появляется ли оно в другом. Как вы видите, появляется ли он в другом массиве? Пройдите через элементы в другом массиве и для каждого из них, посмотрите, совпадает ли его значение со значением, которое вы ищете. Я подозреваю, что вам будет лучше всего работать, пытаясь справиться с этой проблемой самостоятельно, если ваша цель в классе - научиться хорошо писать Java, но вы застряли, можете подумать о том, чтобы обновить свой вопрос с помощью кода которые вы написали, чтобы вы могли получить более подробную обратную связь и указатели в правильном направлении.

Answer 3

Попробуйте это:

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(); 
} 

Answer 4

Если вы хорошо с 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(); 
} 

Answer 5

С дублирующими элементами в пересечении массива.

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); 

Answer 6

Нахождение пересечения включает дубликат, используя карту хеша.

Выход: 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]); 
      } 
     } 
    } 
} 

Answer 7

если массивы сортируются

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]); 
    } 

Answer 8

if the arrays are not sorted 


    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]); 
    }