比较两个数组并获得公共项

时间:2022-01-29 12:13:14

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

我有两个数组,但是它们的长度不同。我想比较这两个数组,并将公共项放到一个新的数组中。同时不应该有重复的项目是第三个数组。我真的搞砸了,请帮帮我。非常感谢……

3 个解决方案

#1


54  

Something like this?

是这样的吗?

NSMutableSet* set1 = [NSMutableSet setWithArray:array1];
NSMutableSet* set2 = [NSMutableSet setWithArray:array2];
[set1 intersectSet:set2]; //this will give you only the obejcts 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.

这个的好处不是查找数组中的对象,而遍历另一个数组,N ^ 2的复杂性,可能需要一段时间,如果数组是大。

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

编辑:set2不必是可变的,不妨只使用它

NSSet* set2 = [NSSet setWithArray:array2];

#2


4  

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:

第三种方法(除了使用set或简单的循环检查包含的每个项)将会对两个数组进行排序,然后使用两个索引:

// 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.

我做了一些简单的分析,如果我对传入的数组进行可变拷贝,并对它们进行排序,它的执行速度将比使用set的方法慢1.5倍。我的方法似乎比使用集合的方法执行速度快1.5倍。如果保证数组已经被排序,那么我的方法将执行得更好(几乎是使用set的版本的4倍),因为不需要排序。

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

这并没有消除重复,所以我在例程的末尾添加了循环。现在它只比使用集合的方法快3倍,但仍然……

#3


2  

Iterate over array1 & search for it in array2. If it is found, add it to array3 if it does not have it already.

遍历array1并在array2中搜索它。如果找到了,将它添加到array3中,如果它还没有。

for (MyObject* obj in array1)
{ 
     if([array2 containsObject:obj] && ![array3 containsObject:obj])
        [array3 addObject:obj];
}

If you array1 does not have duplicate items, you don't need the 2nd check.

如果array1没有重复项,则不需要第二次检查。

HTH,

HTH,

Akshay

阿卡什

#1


54  

Something like this?

是这样的吗?

NSMutableSet* set1 = [NSMutableSet setWithArray:array1];
NSMutableSet* set2 = [NSMutableSet setWithArray:array2];
[set1 intersectSet:set2]; //this will give you only the obejcts 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.

这个的好处不是查找数组中的对象,而遍历另一个数组,N ^ 2的复杂性,可能需要一段时间,如果数组是大。

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

编辑:set2不必是可变的,不妨只使用它

NSSet* set2 = [NSSet setWithArray:array2];

#2


4  

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:

第三种方法(除了使用set或简单的循环检查包含的每个项)将会对两个数组进行排序,然后使用两个索引:

// 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.

我做了一些简单的分析,如果我对传入的数组进行可变拷贝,并对它们进行排序,它的执行速度将比使用set的方法慢1.5倍。我的方法似乎比使用集合的方法执行速度快1.5倍。如果保证数组已经被排序,那么我的方法将执行得更好(几乎是使用set的版本的4倍),因为不需要排序。

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

这并没有消除重复,所以我在例程的末尾添加了循环。现在它只比使用集合的方法快3倍,但仍然……

#3


2  

Iterate over array1 & search for it in array2. If it is found, add it to array3 if it does not have it already.

遍历array1并在array2中搜索它。如果找到了,将它添加到array3中,如果它还没有。

for (MyObject* obj in array1)
{ 
     if([array2 containsObject:obj] && ![array3 containsObject:obj])
        [array3 addObject:obj];
}

If you array1 does not have duplicate items, you don't need the 2nd check.

如果array1没有重复项,则不需要第二次检查。

HTH,

HTH,

Akshay

阿卡什