Intersection of two int array in C#

Question

I am trying to find the intersection of two int array . I am using this code :

  public int[] Find_Common_Elements(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;
    }

    public int[] BubbleSort(int[] numarray)
    {
        int max = numarray.Length;
        for (int i = 1; i < max; i++)
        {
            for (int j = 0; j < max - i; j++)
            {

                if (numarray[j] > numarray[j + 1])
                {
                    int temp = numarray[j];
                    numarray[j] = numarray[j + 1];
                    numarray[j + 1] = temp;
                }
            }
        }
        return numarray;
    }

    public int[] Find_Unique_Elements(int[] numarray)
    {
        BubbleSort(numarray);
        int element = numarray[0];
        int count = 1;
        for (int i = 1; i < numarray.Length; i++)
        {
            if (element == numarray[i])
                continue;
            else
            {
                element = numarray[i];
                count++;
            }
        }

        int[] result = new int[count];

        count = 0;
        element = numarray[0];
        result[count++] = element;
        for (int i = 1; i < numarray.Length; i++)
        {
            if (element == numarray[i])
                continue;
            else
            {
                element = numarray[i];
                result[count++] = element;
            }
        }
        return result;
    }

    public void Result()
    {
        int[] array1 = new int[] { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100,
             95, 85, 75, 65, 55, 45, 35, 25, 15, 05,
             10, 15, 20, 25, 30, 35, 40, 45, 50, 55
        };

        int[] array2 = new int[] { 15, 25, 35, 45, 55,
             12, 22, 32, 43, 52,
             15, 25, 35, 45, 55
        };

        int[] p1 = Find_Unique_Elements(array1);
        int[] p2 = Find_Unique_Elements(array2);
        int[] result = Find_Common_Elements(array1, array2);

        for (int i = 0; i < p1.Length; i++)
            textBox1.Text += "\n" + p1[i].ToString();
        for (int i = 0; i < p2.Length; i++)
            textBox2.Text += "\n" + p2[i].ToString();
        for (int i = 0; i < result.Length; i++)
            textBox3.Text += "\n"+result[i].ToString();
        }








    private void button1_Click(object sender, RoutedEventArgs e)
    {
        Result();
    }

But the problem is that, the result obtained is 15 15 25 25 35 35 45 45 55 55 , and i want 15 25 35 45 55. what is the problem with this code ? Thanks for any help

Answer 1

 static void Main(string[] args)
    {
        int[] one= { 1, 3, 4, 6, 7 };
        int[] second = { 1, 2, 4, 5 };

        foreach (int r in one.Intersect(second))
            Console.WriteLine(r);
        Console.ReadLine();
    }

enjoy

Answer 2

If you want to solve the problem academically, i.e. not to use built-in methods, then here are the two solutions:

1. Sort both arrays. Then make a pass through them similar to Merge sort and print out elements that are equal.

2. Find a pivot in one array (e.g. using Median of Medians algorithm). Then partition each array around that pivot. Then print out as many pivot values as there are in common in two arrays (by doing this you've resolved intersection of the pivot element). Then recursively repeat the operation on left partitions and on right partitions of the two arrays.

EDIT: I was puzzled by this problem from purely algorithmic point of view. Solution #2 is an optimized in-place intersection algorithm, but #1 works faster thanks to smaller constant factor. I've documented the differences and reasoning why sorting is much more efficient in an article, which is a little bit too long for this post: Finding Intersection of Two Unsorted Arrays

Answer 3

Linq is definitely the cleanest way to do this, but that doesn't mean you should throw out your code. It's a great learning tool to question "why doesn't this code do the same thing?"

The answer is remarkably simple. You don't pass the unique arrays into Find_Common_Elements! (Find_Common_Elements has a built-in assumption that the inputs have unique elements, otherwise the behavior would be as expected.) Simply changing this

    int[] result = Find_Common_Elements(array1, array2);

to this:

    int[] result = Find_Common_Elements(p1, p2);

would have made your code work perfectly.

Answer 4

You can use the built-in Linq Intersect extension method for this:

using System.Linq; // Make sure you include this line

public int[] Find_Common_Elements(int[] p1, int[] p2)
{
    return p1.Intersect(p2).ToArray();
}