NSArray：删除具有重复属性的对象

Question

我有一个NSMutableArray包含一些自定义对象。其中两个对象具有相同的属性，如标题和作者。我想删除重复的对象，并离开另一个。

Asset *asset; 
NSMutableArray *items = [[[NSMutableArray alloc] init] autorelease]; 

// First 
asset = [[Asset alloc] init]; 
asset.title = @"Developer"; 
asset.author = @"John Smith"; 
[items addObject:asset]; 
[asset release]; 

// Second 
asset = [[Asset alloc] init]; 
asset.title = @"Writer"; 
asset.author = @"Steve Johnson"; 
[items addObject:asset]; 
[asset release]; 

// Third 
asset = [[Asset alloc] init]; 
asset.title = @"Developer"; 
asset.author = @"John Smith"; 
[items addObject:asset]; 
[asset release]; 

，因为它们不是同一个对象，但只能有重复的特性，我怎么可以删除重复的？

Answer 1

你可以创建一个HashSet，当你循环时，你可以添加“标题+作者”连接集到HashSet（NSMutableSet）。当您到达每个项目时，如果HashSet包含您的密钥，请移除它或不要复制（删除或创建没有重复的副​​本）。

这使得阶数n（1个循环）

这里的的NSMutableSet类：

http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSMutableSet_Class/Reference/NSMutableSet.html#//apple_ref/occ/cl/NSMutableSet

EDIT与代码：

代码的肉是一个环。

void print(NSMutableArray *assets) 
{ 
    for (Asset *asset in assets) 
    { 
     NSLog(@"%@/%@", [asset title], [asset author]); 
    } 
} 

int main (int argc, const char * argv[]) 
{ 

    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init]; 

    // 
    // Create the initial data set 
    // 
    Asset *asset; 
    NSMutableArray *items = [[[NSMutableArray alloc] init] autorelease]; 

    // First 
    asset = [[Asset alloc] init]; 
    asset.title = @"Developer"; 
    asset.author = @"John Smith"; 
    [items addObject:asset]; 
    [asset release]; 

    // Second 
    asset = [[Asset alloc] init]; 
    asset.title = @"Writer"; 
    asset.author = @"Steve Johnson"; 
    [items addObject:asset]; 
    [asset release]; 

    // Third 
    asset = [[Asset alloc] init]; 
    asset.title = @"Developer"; 
    asset.author = @"John Smith"; 
    [items addObject:asset]; 
    [asset release]; 

    NSLog(@"****Original****"); 
    print(items); 

    // 
    // filter the data set in one pass 
    // 
    NSMutableSet *lookup = [[NSMutableSet alloc] init]; 
    for (int index = 0; index < [items count]; index++) 
    { 
     Asset *curr = [items objectAtIndex:index]; 
     NSString *identifier = [NSString stringWithFormat:@"%@/%@", [curr title], [curr author]]; 

     // this is very fast constant time lookup in a hash table 
     if ([lookup containsObject:identifier]) 
     { 
      NSLog(@"item already exists. removing: %@ at index %d", identifier, index); 
      [items removeObjectAtIndex:index]; 
     } 
     else 
     { 
      NSLog(@"distinct item. keeping %@ at index %d", identifier, index); 
      [lookup addObject:identifier]; 
     } 
    } 

    NSLog(@"****Filtered****"); 
    print(items); 

    [pool drain]; 
    return 0; 
} 

下面是输出：

Craplet[11991:707] ****Original**** 
Craplet[11991:707] Developer/John Smith 
Craplet[11991:707] Writer/Steve Johnson 
Craplet[11991:707] Developer/John Smith 
Craplet[11991:707] distinct item. keeping Developer/John Smith at index 0 
Craplet[11991:707] distinct item. keeping Writer/Steve Johnson at index 1 
Craplet[11991:707] item already exists. removing: Developer/John Smith at index 2 
Craplet[11991:707] ****Filtered**** 
Craplet[11991:707] Developer/John Smith 
Craplet[11991:707] Writer/Steve Johnson 

Answer 2

这是你能做到这一点 一个方法：

NSMutableArray* toRemove = [NSMutableArray array]; 

    for (Asset* asset1 in items) 
    { 
     for (Asset* asset2 in items) 
     { 
      if (asset1 != asset2) 
      { 
       if ([asset1.title isEqualToString:asset2.title] && [asset1.author isEqualToString:asset2.author]) 
       { 
        [toRemove addObject:asset2]; 
       } 
      } 
     } 
    } 

    for (Asset* deleted in toRemove) 
    { 
     [items removeObject:toRemove]; 
    } 

Answer 3

首先，我会重写isEqual：方法方法资产是这样的：

-(BOOL)isEqual:(Asset *)otherAsset { 
    return [self.title isEqual:otherAsset.title] && [self.author isEqual:otherAsset.author]; 
} 

然后，如果你想避免将重复排列在首位：

NSUInteger idx = [items indexOfObject:asset]; // tests objects for equality using isEqual: 
if (idx == NSNotFound) [items addObject:asset]; 

如果数组已经包含重复，那么发现他们有一个运行时间已经比线性差，但我认为，任何算法创建一个新的数组并且只添加上面的独特元素是最好的算法。事情是这样的：

NSMutableArray *itemsWithUniqueElements = [NSMutableArray arrayWithCapacity:[items count]]; 

for (Asset *anAsset in items) { 
    if ([items indexOfObject:anAsset] == NSNotFound) 
     [itemsWithUniqueElements addObject:anAsset]; 
} 

[items release]; 
items = [itemsWithUniqueElements retain]; 

在最坏的情况下（所有元素都已经是唯一的）迭代的次数是：

1 + 2 + 3 + ... + n = n * (n+1)/2 

仍然是O（n^2），但略好于@Justin Meiners'算法。没有冒犯的意思！ :)

Answer 4

您可以使用NSSet的唯一性从原始数组中获取不同的项目。如果您有源代码Assest，则需要覆盖Asset类中的hash和isEqual:方法。

@interface Asset : NSObject 
@property(copy) NSString *title, *author; 
@end 

@implementation Asset 
@synthesize title, author; 

-(NSUInteger)hash 
{ 
    NSUInteger prime = 31; 
    NSUInteger result = 1; 

    result = prime * result + [self.title hash]; 
    result = prime * result + [self.author hash]; 

    return result; 
} 

-(BOOL)isEqual:(id)object 
{ 
    return [self.title isEqualToString:[object title]] && 
    [self.author isEqualToString:[object author]]; 
} 

- (void)dealloc { 
    [title release]; 
    [author release]; 
    [super dealloc]; 
} 

@end 

然后执行：

Asset *asset; 
NSMutableArray *items = [[[NSMutableArray alloc] init] autorelease]; 

// First 
asset = [[Asset alloc] init]; 
asset.title = @"Developer"; 
asset.author = @"John Smith"; 
[items addObject:asset]; 
[asset release]; 

// Second 
asset = [[Asset alloc] init]; 
asset.title = @"Writer"; 
asset.author = @"Steve Johnson"; 
[items addObject:asset]; 
[asset release]; 

// Third 
asset = [[Asset alloc] init]; 
asset.title = @"Developer"; 
asset.author = @"John Smith"; 
[items addObject:asset]; 
[asset release]; 

NSLog(@"Items: %@", items); 

NSSet *distinctItems = [NSSet setWithArray:items]; 

NSLog(@"Distinct: %@", distinctItems); 

如果你需要在最后一个数组，你可以叫[distinctItems allObjects]

Answer 5

如果您想您的自定义NSObject的子类被视为相等时他们的名字相同，你可以执行isEqual:和hash。这将允许您将对象添加到NSSet/NSMutableSet（一组不同的对象）。

然后，您可以使用NSSet的sortedArrayUsingDescriptors:方法轻松创建排序的NSArray。

MikeAsh写了一篇关于实现定制平等的一个非常坚实的一块：Friday Q&A 2010-06-18: Implementing Equality and Hashing