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

Question

我正在尝试创建一种方法，该方法通过重复对两个数组进行交集。

示例:{1,2,5,4,1,3} 和 {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.* 或 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) 复杂度。