16

I'm currently enumerating through NSMutableArray (or NSMutableSet) elements to find duplicates and remove them.

For example, if array/set has values [@"a", @"b", @"b", @"c"], the end result should be [@"a", @"b", @"c"].

Since I'm comparing NSStrings, I'm using isEqualTo: method to check if strings are equal.

Is there a more efficient way to do remove duplicate entries than to loop through all of them and check if duplicate exists?

elp
  • 8,021
  • 7
  • 61
  • 120
Rudi
  • 2,450
  • 5
  • 26
  • 37

4 Answers4

43

An NSSet does exactly what you're trying to do: it is a (unordered) collection of unique items. So, you can find the unique items in your array like so:

NSSet *uniqueElements = [NSSet setWithArray:myArray];

// iterate over the unique items
for(id element in uniqueElements) {
  // do something
}

NSSet most likely uses a hash algorithm to make insertion O(1) (compared to O(n^2) to check if each item is unique by iteration), but the Apple documentation does not make such a guarantee so you probably shouldn't count on that implementation detail.

If, for some reason you need to keep the unique items in a sorted (ordered) collection, you can turn the set back into an array with -[NSSet allObjects] and then sort the resulting array.

Barry Wark
  • 107,306
  • 24
  • 181
  • 206
  • Thank you, that worked! I did this to get unique elements in the array: // add to set to check for unique element names NSSet *uniqueNames = [NSSet setWithArray:names]; // return data back to the array names = [[NSMutableArray alloc] initWithArray:[uniqueNames allObjects]]; – Rudi Jul 22 '09 at 04:44
  • The more cannonical way to get back to the array names would be: id names = [[uniqueNames allObjects] retain]; //if you want to keep names or id names = [uniqueNames allObjects]; //if you don't want to retain ownership of the array – Barry Wark Jul 22 '09 at 05:16
  • @BarryWark wouldn't it be O(n) for the iteration? – Rui Peres Jul 25 '13 at 14:27
  • @JackyBoy my algorithms classes are a lot of years ago now, but I believe inserting `m` elements into an `n` element array naively (i.e. the array is unsorted) would be `O(m*n) ~ O(n^2)`, but please correct the post if I'm wrong! – Barry Wark Jul 25 '13 at 18:52
  • From my understanding, it don't think you can `O(m*n) ~ O(n^2)` only if `m -> n` (worst case possible). But normally I think that what Big O considers is the bigger one between `m` and `n`. I might be wrong, just did want to confirm with you actually. – Rui Peres Jul 25 '13 at 19:04
  • @JackyBoy I *think* you're right. In this case (finding duplicates), it's m = n, however, no? – Barry Wark Jul 25 '13 at 19:56
  • If n `@[1,3,5,7,8]` and m `@[2,4,6,8]` and you want to insert m into n : You will need @ minimum 2 cycles inside each other. But in that case where you want to check if a given array doesn't has any duplicates it would be `O(n^2)`. You are right! – Rui Peres Jul 25 '13 at 20:46
5

An NSSet or NSMutableSet will guarantee that you don't have duplicate objects. It will work for NSStrings as in your example, but for your own classes keep in mind what do you mean by "equal" and implement the hash and isEqual: methods accordingly.

Marco Mustapic
  • 3,879
  • 1
  • 21
  • 20
  • Thank you for the explanation, it's good to know that it's automatic for NSStrings. – Rudi Jul 22 '09 at 04:45
3

A set never contains duplicate elements, so simply creating an NSMutableSet should guarantee uniqueness of values.

Daniel Dickison
  • 21,832
  • 13
  • 69
  • 89
1

Only this line of code will work fine .

NSSet *mySet = [NSSet setWithArray:myArray];

now mySet will have unique elements.

elp
  • 8,021
  • 7
  • 61
  • 120
Chandramani
  • 871
  • 1
  • 12
  • 11