Как найти пересечение двух массивов с дублирующими элементами?

Question

Нужно вывести пересечение двух отсортированных массивов с дублирующими элементами.

На выходе (10, 10, 24, 24), а нужно (10, 24).

import java.util.Arrays;

public class ClassesAndObjects {
     public static void main(String[] args) {
        int[] numbers1 = {10, 10, 13, 14, 18, 24, 24, 30};
        int[] numbers2 = {10, 10, 11, 24, 24};
        int[] result1 = ClassesAndObjects.getIntersectionOfSortedArrays(numbers1, numbers2);
        System.out.println(Arrays.toString(result1));
    }

    public static int[] getIntersectionOfSortedArrays(int[] arr1, int[] arr2) {
        int i = 0, j = 0;
        int n = arr1.length;
        int m = arr2.length;
        int[] intersection = new int[Math.min(n, m)];
        int index = 0;
    
        while (i < n && j < m) {
            if (arr1[i] == arr2[j]) {
                intersection[index++] = arr1[i];
                i++;
                j++;
            } else if (arr1[i] < arr2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return Arrays.copyOf(intersection, index);
    }
}

Answer 1

Например, проверять, что такое значение уже есть:

 if (arr1[i] == arr2[j]) {
            if (index == 0 || arr1[i] != intersection[index-1]) {
                intersection[index++] = arr1[i];
            }   
            i++;
            j++;

Answer 2

В дополнение к ответу MBo, также можно пропускать возможные дубликаты в обоих входных массивах при обнаружении совпадения:

public static int[] getIntersectionOfSortedArrays(int[] arr1, int[] arr2) {
    int n = arr1.length;
    int m = arr2.length;
    int[] intersection = new int[Math.min(n, m)];
    int index = 0;
    
    for (int i = 0, j = 0; i < n && j < m; ) {
        int v1 = arr1[i]; 
        if (v1 == arr2[j]) {
            intersection[index++] = v1;
            while (++i < n && arr1[i] == v1);
            while (++j < m && arr2[j] == v1);
        } else if (v1 < arr2[j]) {
            i++;
        } else {
            j++;
        }
    }

    return Arrays.copyOf(intersection, index);
}

Answer 3

Есть очень много способов вывести пересечение двух массивов, например вот так:

      int[] arr1 = {10, 10, 13, 14, 18, 24, 24, 30};
      int[] arr2 = {10, 10, 11, 24, 24};
      
      Set<Integer> set = new TreeSet<>();
      for (int i = 0; i < arr2.length; i++) {
          if (Arrays.binarySearch(arr1, arr2[i]) >= 0) {
              set.add(arr2[i]);
          }
      }
      System.out.println(set);

// результат [10, 24]

binarySearch работает только с отсортированными массивами, по условию задачи массив уже отсортирован. Если нет, то надо будет еще сортировку добавить

БЛОГ НА HUSL

Как найти пересечение двух массивов с дублирующими элементами?

Ответы (3 шт):