Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Intersection of two arrays with repetition

Tags:

java

algorithm

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.*?

like image 280
Alex Avatar asked Nov 30 '12 09:11

Alex


People also ask

What is meant by intersection of two arrays?

The intersection of two arrays is a list of distinct numbers which are present in both the arrays. The numbers in the intersection can be in any order. For example. Input: A[] = {1,4,3,2,5, 8,9} , B[] = {6,3,2,7,5} Output: {3,2,5}

How do you find the intersection of two arrays in CPP?

Similarly, intersection of two arrays will be denoted by A ∩ B. It is an array of the elements that are present in both the given arrays. For this, we will traverse through the elements of the first array one by one. Simultaneously we will be checking if that element is present in the second array or not.


1 Answers

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.

like image 103
Толя Avatar answered Sep 23 '22 19:09

Толя