Intersection of two arrays with repetition

Question

I'm trying to create a method that does intersection of two arrays with repetition.

Example: {1,2,5,4,1,3} and {1,2,1} -> {1,1,2}.

I have a method that does intersection but without repetition.

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

How can I add repetitions without using Arrays.* or List.*?

Answer 1

Please try following function:

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

If necessary you also should apply sorting, this solution has O(N^2) complexity. Also possible made O(NLogN) complexity.