java - 重复的两个数组的交集

Question

我正在尝试创建一种方法，该方法可以重复两个数组的交集。

例子：{1,2,5,4,1,3} and {1,2,1} -> {1,1,2}.

我有一种方法可以交叉但不重复。

  public int[] findSameElements(int[] p1, int[] p2) {
    int count = 0;
    for (int i = 0; i < p1.length; i++) {
      for (int j = 0; j < p2.length; j++) {
        if (p1[i] == p2[j]) {
          count++;
          break;
        }
      }
    }

    int[] result = new int[count];
    count = 0;
    for (int i = 0; i < p1.length; i++) {
      for (int j = 0; j < p2.length; j++) {
        if (p1[i] == p2[j]) {
          result[count++] = p1[i];
          break;
        }
      }
    }

    return result;
  }

如何在不使用Arrays.*or的情况下添加重复List.*？

Answer 1

请尝试以下功能：

public int[] findSameElements(int[] p1, int[] p2)
{
    int count = 0;
    bool[] choosen = new bool[p2.length];

    for (int i = 0; i < p1.length; i++)
    {
        for (int j = 0; j < p2.length; j++)
        {
            if (!choosen[j] && p1[i] == p2[j])
            {
                choosen[j] = true;
                count++;
                break;
            }
        }
    }

    int[] result = new int[count];
    count = 0;
    for (int i = 0; i < p2.length; i++)
    {
        if (choosen[i])
        {
            result[count] = p2[i];
            count++;
        }
    }

    return result;
}

如有必要，您还应该应用排序，此解决方案具有 O(N^2) 复杂性。也可能使 O(NLogN) 复杂度。

Answer 2

您可以构建直方图（将表示为 a Map<Integer,Integer>）并且：

1. 将 list1 中的所有元素（及其重复次数）插入直方图
2. 为每个元素 e 迭代 list2：
   - 如果直方图包含元素 e（具有正值）：打印（或附加到新列表）e，并减少直方图中 e 的值

请注意，此解决方案是O(n+m)时间（平均情况）和O(min{n,m})空间。

---

代码示例（使用List<T>而不是数组 - 但当然可以轻松修改）：

private static <T> Map<T,Integer>  populateHistogram(List<T> list) {
    Map<T,Integer> histogram = new HashMap<T, Integer>();
    for (T e : list) {
        Integer val = histogram.get(e);
        histogram.put(e, val == null ? 1 : val+1);
    }
    return histogram;
}
public static <T> List<T> generateInterectionList(List<T> list,Map<T,Integer> histogram ) {
    List<T> res = new ArrayList<T>();
    for (T e : list) { 
        Integer val = histogram.get(e);
        if (val != null && val > 0) { 
            res.add(e);
            histogram.put(e,val - 1);
        }
    }
    return res;
}
public static <T> List<T> getIntersection(List<T> list1, List<T> list2) {
    Map<T,Integer> histogram = populateHistogram(list1.size() > list2.size() ? list2 : list1);
    return generateInterectionList(list1.size() > list2.size() ? list2 : list1,histogram);
}
public static void main(String[]args){
    List<Integer> list1 = Arrays.asList(new Integer[]{1,2,5,4,1,3}); 
    List<Integer> list2 = Arrays.asList(new Integer[]{1,2,1}); 
    System.out.println(getIntersection(list1, list2));
}

---

请注意，它也可以在O(nlogn)时间和O(logn)空间上完成（用于排序算法的堆栈跟踪），对列表进行排序，然后为每个列表使用一个指针并行迭代

伪代码：

在 i1 < list1.length 和 i2 < list2.length 时重复：

1. if list1[i1] == list2[i2]:
   - 打印 list1[i1]
   - 增加 i1,i2
2. else if list1[i1] > list2[i2]:
   - 增加 i2
3. 否则：
   - 增加 i1

Answer 3

有理由不使用集合吗？该retainAll(...)方法可以满足您的要求：

List<Integer> list1 = ...
List<Integer> list2 = ...
List<Integer> intersection = list1.retainAll( list2 );

Answer 4

一种方法是使用哈希表。从两个数组中创建两个单独的哈希表。键值对是（元素，计数）。现在遍历较小的哈希表并打印出每个元素 count_min 的次数，其中 count_min = min（表 a 中元素的计数，表 b 中的元素计数）。这是一种具有额外空间复杂度的线性算法。

空间复杂度 = O(n+m) 其中 n 和 m 是两个数组的大小。时间复杂度 O(n)，其中 n > m。

Answer 5

如果您对 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();
}