Java, znaleźć punkt przecięcia dwóch tablic

Question

już przeczytać kilka innych wątków przepełnienie stosu na ten temat:

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

próbuję zbadać dwie tablice, a także ich liczba elementów (numElementsInX i numElementsInY) i zwraca nową tablicę zawierającą wspólne wartości tablic x i y. Ich przecięcie.

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} 

Przeczytałem, że muszę użyć algorytmu LCS. Czy ktoś może dać mi przykład, jak to zrobić? Zarówno tablica jak i wartości w tablicy są inicjowane i generowane w innej metodzie, a następnie przekazywane do przecięcia.

Każda pomoc/wyjaśnienie jest mile widziane.

CODE EDIT

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

Najprostszym rozwiązaniem byłoby użycie zestawów, tak długo jak nie obchodzi mnie, że elementy w rezultacie będzie mieć inną kolejność, a duplikaty zostaną usunięte . Macierze wejściowe array1 i array2 są Integer[] subarrays danego int[] macierzy odpowiadającej liczbie elementów, które zamierzają procesu:

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

Powyższy zwróci Integer[], jeśli potrzebne jest to proste do skopiowania i przekształcenia jej zawartość do int[].

Answer 2

Jeśli nie chcesz używać innych struktur danych, takich jak zestaw, podstawową ideą jest to, że chcesz powtórzyć elementy jednej z tablic i dla każdej wartości sprawdzić, czy pojawia się ona w drugiej. Jak widzisz, czy pojawia się w innej tablicy? Przejdź przez elementy w drugiej tablicy i dla każdego sprawdź, czy jego wartość jest równa wartości, której szukasz. Podejrzewam, że najlepiej będzie ci służyć, próbując samodzielnie rozwiązać ten problem poza tym punktem, jeśli twoim celem w zajęciu klasy jest nauczenie się pisania dobrze języka Java, ale utkniesz, możesz rozważyć aktualizację swojego pytania za pomocą kodu które napisałeś, abyś mógł uzyskać bardziej szczegółowe informacje zwrotne i wskazówki we właściwym kierunku.

Answer 3

Spróbuj tego:

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

Jeśli są w porządku z java-8, to najprostsze rozwiązanie można myślę, jest za pomocą strumieni i filtr. Implementacja jest następująca:

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

Z duplikatami elementów w skrzyżowaniu znajdującym tablicę.

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

znalezione skrzyżowanie zawiera duplikat przy użyciu mapy skrótów.

wyjściowa: 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

jeśli macierze są klasyfikowane

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