Java, найти пересечение двух массивов
Я уже прочитал несколько других потоков:
чтобы найти пересечение двух мультимножеств в java
Как получить пересечение между двумя массивами как новый массив?
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{
}
}
}
Ответы
Ответ 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[].
Ответ 2
Если вы в порядке с 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();
}
Ответ 3
Если вы не хотите использовать другие структуры данных, такие как набор, то основная идея заключается в том, что вы хотите итерации по элементам одного из массивов, и для каждого значения посмотрите, появляется ли оно в другом. Как вы видите, появляется ли он в другом массиве? Пройдите через элементы в другом массиве и для каждого из них, посмотрите, совпадает ли его значение со значением, которое вы ищете. Я подозреваю, что вам будет лучше всего работать, пытаясь справиться с этой проблемой самостоятельно, если ваша цель в классе - научиться хорошо писать Java, но вы застряли, можете подумать о том, чтобы обновить свой вопрос с помощью кода которые вы написали, чтобы вы могли получить более подробную обратную связь и указатели в правильном направлении.
Ответ 4
Попробуйте следующее:
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();
}
Ответ 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);
Ответ 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]);
}
}
}
}
Ответ 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]);
}
Ответ 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]);
}
Ответ 9
Как найти пересечение 3 несортированных массивов в Java: -
Я использовал подход Core Java с использованием for loop & используя 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);
}
}
Ответ 10
Если вы когда-нибудь хотели реализовать это в 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))
Ответ 11
Вы можете найти пересечение двух массивов с помощью:
T[] result = Arrays.stream(a1)
.filter(new HashSet<>(Arrays.asList(a2))::contains)
.toArray(T[]::new);
где T должен быть заменен ссылочным типом, например, 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]);
