compare two arrays and get the common items

Question

I have two arrays, but they have different lengths. I want to compare these two arrays and put common items to a new array. meanwhile there should not be have duplicate items is the third array. I really mess up with this, please give me a help. highly thankful . . .

Answer 1

Something like this?

NSMutableSet* set1 = [NSMutableSet setWithArray:array1];
NSMutableSet* set2 = [NSMutableSet setWithArray:array2];
[set1 intersectSet:set2]; //this will give you only the objects that are in both sets

NSArray* result = [set1 allObjects];

This has the benefit of not looking up the objects in the array, while looping through another array, which has N^2 complexity and may take a while if the arrays are large.

Edit: set2 doesn't have to be mutable, might as well use just

NSSet* set2 = [NSSet setWithArray:array2];

Answer 2

A third approach (besides using sets or the simple loop checking each item with contains) would be to sort both arrays, and then use two indices:

// approach using sets:

NSArray *arrayUsingSets(NSMutableArray *arr1, NSMutableArray *arr2)
{
    NSMutableSet *set1 = [NSMutableSet setWithArray: arr1];
    NSSet *set2 = [NSSet setWithArray: arr2];
    [set1 intersectSet: set2];
    return [set1 allObjects];
}

// my approach:

NSArray *arrayUsingComp(NSMutableArray *arr1, NSMutableArray *arr2)
{
    NSMutableArray *results = [NSMutableArray arrayWithCapacity: arr1.count + arr2.count];

    // Assumes input arrays are sorted. If not, uncomment following two lines.
//    [arr1 sortUsingSelector: @selector(compare:)];
//    [arr2 sortUsingSelector: @selector(compare:)];

    int i = 0;
    int j = 0;
    while ((i < arr1.count) && (j < arr2.count))
    {
        switch ([[arr1 objectAtIndex: i] compare: [arr2 objectAtIndex: j]])
        {
            case NSOrderedSame:
                [results addObject: [arr1 objectAtIndex: i]];
                i++, j++;
                break;
            case NSOrderedAscending:
                i++;
                break;
            case NSOrderedDescending:
                j++;
                break;
         }
    }

    // NOTE: results are sorted too.
    // NOTE 2: loop must go "backward".
    for (NSInteger k = results.count - 1; k > 0; k--) 
        if ([[results objectAtIndex: k] isEqual: [results objectAtIndex: k-1]])
            [results removeObjectAtIndex: k];

    return results;    
}

I did some simple profiling, and if I make mutable copies of the arrays passed in, and sort those, it performs 1.5 times slower than the approach using sets. My approach above seems to perform 1.5 times faster than the approach using sets. If the arrays are guaranteed to be sorted already, my approach will perform even better yet (almost 4 times as fast as the version using sets), since no sorting is required.

Update:

This did not eliminate duplicates, so I added the loop at the end of the routine. Now it is only 3 times as fast as the approach using sets, but still...