在Objective-C中从NSMutableArray中删除重复值的最佳方法是什么？

Question

NSString从NSMutableArrayObjective-C中删除重复值()的最佳方法是什么？

这是最简单正确的方法吗？

uniquearray = [[NSSet setWithArray:yourarray] allObjects];

Answer 1

NSSet如果您不担心对象的顺序,那么您的方法是最好的,但是如果您不担心订单,那么为什么不将它们存储在一个NSSet开头？

我在2009年写下了这个答案; 在2011年,Apple加入NSOrderedSet了iOS 5和Mac OS X 10.7.算法现在是两行代码:

NSOrderedSet *orderedSet = [NSOrderedSet orderedSetWithArray:yourArray];
NSArray *arrayWithoutDuplicates = [orderedSet array];

如果您担心订单而且您在iOS 4或更早版本上运行,请循环遍历该阵列的副本:

NSArray *copy = [mutableArray copy];
NSInteger index = [copy count] - 1;
for (id object in [copy reverseObjectEnumerator]) {
    if ([mutableArray indexOfObject:object inRange:NSMakeRange(0, index)] != NSNotFound) {
        [mutableArray removeObjectAtIndex:index];
    }
    index--;
}
[copy release];

Answer 2

我知道这是一个老问题,但NSArray 如果你不关心订单,有一种更优雅的方法可以删除重复项.

如果我们使用Key Value Coding中的Object Operators,我们可以这样做:

uniquearray = [yourarray valueForKeyPath:@"@distinctUnionOfObjects.self"];

由于AnthoPak还指出可以根据属性删除重复项.一个例子是:@distinctUnionOfObjects.name

Answer 3

是的,使用NSSet是一种明智的方法.

要添加Jim Puls的答案,这里有一种在保留订单的同时剥离重复项的替代方法:

// Initialise a new, empty mutable array 
NSMutableArray *unique = [NSMutableArray array];

for (id obj in originalArray) {
    if (![unique containsObject:obj]) {
        [unique addObject:obj];
    }
}

它基本上与Jim的方法相同,但将独特的项目复制到新的可变数组而不是从原始数据中删除重复项.这使得在具有大量重复的大型数组(不需要复制整个数组)的情况下,它的内存效率稍高,并且在我看来更具可读性.

请注意,在任何一种情况下,检查项目是否已包含在目标数组中(containsObject:在我的示例中使用,或indexOfObject:inRange:在Jim中)都不能很好地扩展到大型数组.这些检查在O(N)时间运行,这意味着如果您将原始数组的大小加倍,则每次检查将花费两倍的时间来运行.由于您正在检查数组中的每个对象,因此您还将运行更多这些更昂贵的检查.整个算法(我的和Jim都是)在O(N ²)时间内运行,随着原始阵列的增长,这会很快变得昂贵.

为了将其降低到O(N)时间,您可以使用a NSMutableSet来存储已添加到新数组的项目的记录,因为NSSet查找是O(1)而不是O(N).换句话说,无论元素集中有多少元素,检查元素是否是NSSet的成员都需要相同的时间.

使用这种方法的代码看起来像这样:

NSMutableArray *unique = [NSMutableArray array];
NSMutableSet *seen = [NSMutableSet set];

for (id obj in originalArray) {
    if (![seen containsObject:obj]) {
        [unique addObject:obj];
        [seen addObject:obj];
    }
}

这仍然有点浪费; 当问题清楚地表明原始数组是可变的时,我们仍然在生成一个新数组,因此我们应该能够对其进行重复数据删除并节省一些内存.像这样的东西:

NSMutableSet *seen = [NSMutableSet set];
NSUInteger i = 0;

while (i < [originalArray count]) {
    id obj = [originalArray objectAtIndex:i];

    if ([seen containsObject:obj]) {
        [originalArray removeObjectAtIndex:i];
        // NB: we *don't* increment i here; since
        // we've removed the object previously at
        // index i, [originalArray objectAtIndex:i]
        // now points to the next object in the array.
    } else {
        [seen addObject:obj];
        i++;
    }
}

更新:Yuri Niyazov 指出我的最后答案实际上是在O(N ²)中removeObjectAtIndex:运行,因为可能在O(N)时间运行.

(他说"可能"因为我们不确定它是如何实现的;但是一种可能的实现是在删除索引X处的对象之后,该方法然后循环遍历索引X + 1中的每个元素到数组中的最后一个对象,将它们移动到上一个索引.如果是这种情况,则确实是O(N)性能.)

那么该怎么办？这取决于实际情况.如果你有一个大型阵列并且你只需要少量的重复数据,那么就地重复数据删除工作就可以正常工作,而且你需要建立一个重复的数组.如果你有一个数组,你期望有很多重复,那么构建一个单独的,去掉的数组可能是最好的方法.这里的内容是big-O表示法仅描述算法的特征,它不会明确地告诉您哪种情况最适合任何特定情况.

Answer 4

适用于OS X v10.7及更高版本.

如果你担心订单,正确的方法

NSArray *no = [[NSOrderedSet orderedSetWithArray:originalArray]allObjects];

以下是在Order中从NSArray中删除重复值的代码.

Answer 5

如果您的目标是iOS 5+(涵盖整个iOS世界),请尽量使用NSOrderedSet.它会删除重复项并保留您的顺序NSArray.

做就是了

NSOrderedSet *orderedSet = [NSOrderedSet orderedSetWithArray:yourArray];

您现在可以将其转换回唯一的NSArray

NSArray *uniqueArray = orderedSet.array;

或者只使用orderedSet,因为它具有与NSArray相同的方法objectAtIndex:,firstObject依此类推.

会员检查的contains速度甚至NSOrderedSet比它更快NSArray

有关结帐,请参阅NSOrderedSet参考

Answer 6

需要订单

NSArray *yourarray = @[@"a",@"b",@"c"];
NSOrderedSet *orderedSet = [NSOrderedSet orderedSetWithArray:yourarray];
NSArray *arrayWithoutDuplicates = [orderedSet array];
NSLog(@"%@",arrayWithoutDuplicates);

或者不需要订购

NSSet *set = [NSSet setWithArray:yourarray];
NSArray *arrayWithoutOrder = [set allObjects];
NSLog(@"%@",arrayWithoutOrder);