ObjC: count of each string in an array?

Question

Say I have an NSArray:

@[@"Hello", @"World", @"Hello"]

Since there are two 'Hello's, I need to convert the array into:

@[@"Hello(1)", @"World", @"Hello(2)"]

So 'Hello' has number appended, but 'World' won't have (1) appended as there is only one.

I know I can create a dictionary with the words as keys and iterate through the array, increment the count as their values, but is there a better way?

edit:

Yes I do need the result array to have the same order for words as the input array, the reason for this is that I'm making a vocabulary app for non-English speaking students, one of the feature is to have a translation(in their own language) of a sentence and a list of shuffled words for the sentence, they can then choose the words in the correct order from the list. So you may see the translation of 'How do you do?' in another language and the list of words: 'do' 'you' 'how' 'do', and the students need to select the words in the order of 'How do you do?', that's why I need to distinguish the order of same words.

Nothing wrong, that is a straight forward way I can think of, I'm not a smart person, usually the first solution comes up in my mind is a dumb stupid brute-force like solution. So I wonder is there any better ones. Also, re-construct the second array from the dictionary is also not efficient. — Heuristic
– Heuristic, Commented Aug 25, 2013 at 0:53
Do you need the output array to be in the same order as the original (just with the numbers appended)? Also, can you explain why you think you need this -- maybe there's a better structure you haven't thought of. — rdelmar
– rdelmar, Commented Aug 25, 2013 at 1:10
Straight-forward is goodness. It's often better to use a simple, straight-forward technique even when there's a "clever" one that is faster or otherwise "better". Been programming 40 years and straight-forward is still my preference. — Hot Licks
– Hot Licks, Commented Aug 25, 2013 at 2:27
Ok I made something that meets all the requirements... just because. I think it's fast too. — nielsbot
– nielsbot, Commented Aug 25, 2013 at 2:35

nielsbot · Accepted Answer · 2013-08-25 02:34:31Z

2

Maybe use an NSCountedSet (which is equivalent of a what you might implement with NSDictionary)

-(NSArray*)renameStrings:(NSArray*)strings
{
    NSCountedSet * set = [ [ NSCountedSet alloc ] initWithArray:strings ];

    NSMutableArray * result = [ NSMutableArray arrayWithCapacity:[ strings count ] ] ;

    for( id object in set )
    {
        NSUInteger count = [ set countForObject:object ] ;
        if ( count == 1 )
        {
            [ result addObject:object ] ;
        }
        else
        {
            NSUInteger index= 0 ;
            while( index < count )
            {
                ++index ;
                [ result addObject:[ NSString stringWithFormat:@"%@(%lu)", object, index ] ] ;
            }
        }
    }

    return result ;
}

(The result may be ordered differently than the input)

Addendum:

Here's a one-pass solution that also maintains the order of the input (just for "fun"):

struct Tree
{
    struct Tree * left ;
    struct Tree * right ;
    NSUInteger count ;
    NSUInteger firstIndex ;
    CFStringRef value ;
};

void TreeInsert( struct Tree * tree, NSMutableArray * resultArray, NSString * stringToInsert, NSUInteger stringIndex )
{
    switch( CFStringCompare( (__bridge CFStringRef)stringToInsert , tree->value, 0 ) )
    {
        case NSOrderedAscending:
        {
            if ( tree->right )
            {
                TreeInsert( tree->right, resultArray, stringToInsert ,stringIndex ) ;
            }
            else
            {
                tree->right = malloc( sizeof( struct Tree ), 1 ) ;
                *tree->right = (struct Tree){ NULL, NULL, 1, stringIndex, CFBridgingRetain( stringToInsert ) } ;
                [ resultArray addObject:stringToInsert ] ;
            }
            break ;
        }
        case NSOrderedDescending:
        {
            if ( tree->left )
            {
                TreeInsert( tree->left, resultArray, stringToInsert ,stringIndex ) ;
            }
            else
            {
                tree->left = malloc( sizeof( struct Tree ), 1 ) ;
                *tree->left = (struct Tree){ NULL, NULL, 1, stringIndex, CFBridgingRetain( stringToInsert ) } ;
                [ resultArray addObject:stringToInsert ] ;
            }
            break ;
        }
        default:
        {
            ++tree->count ;
            if ( tree->firstIndex != NSNotFound )
            {
                NSString * string = [ NSString stringWithFormat:@"%@(1)", [ resultArray objectAtIndex:tree->firstIndex ] ] ;
                [ resultArray replaceObjectAtIndex:tree->firstIndex withObject:string ] ;
                tree->firstIndex = NSNotFound ;
            }
            [ resultArray addObject:[ NSString stringWithFormat:@"%@(%lu)", stringToInsert, tree->count ] ] ;
            break ;
        }
    }
}

void DisposeTree( struct Tree * tree )
{
    if ( tree->left ) { DisposeTree( tree->left ) ; }
    if ( tree->right ) { DisposeTree( tree->right ) ; }
    if ( tree->value ) { CFRelease( tree->value ) ; }

    free( tree ) ;
}

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

    @autoreleasepool {

        NSArray * array = @[ @"Hello", @"Goodbye", @"Hello", @"Something else" ] ;
        NSMutableArray * result = [ NSMutableArray arrayWithCapacity:array.count ] ;

        struct Tree * tree = NULL ;

        NSEnumerator * enumerator = [ array objectEnumerator ] ;

        {
            NSString * firstString = [ enumerator nextObject ] ;
            tree = malloc( sizeof( struct Tree ), 1 ) ;
            *tree = (struct Tree){ NULL, NULL, 1, 0, CFBridgingRetain( firstString ) } ;
            [ result addObject:firstString ] ;
        }

        NSUInteger index = 1 ;
        for( NSString * string in enumerator )
        {
            TreeInsert( tree, result, string, index ) ;
            ++index ;
        }

        NSLog(@"result=%@\n", result ) ;
    }
}

edited Aug 25, 2013 at 2:34

answered Aug 25, 2013 at 0:59

nielsbot

16k4 gold badges53 silver badges75 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Heuristic Over a year ago

Thanks, but in your code you have a while loop inside a for loop, looks like it is not more efficient then just a dictionary.

Aaron Brager Over a year ago

@hzxu This solution would only go through each object only once.

nielsbot Over a year ago

BTW--I don't think it's possible to do a one pass solution, because you require that unique words never have the count appended. You will always have to check the entire set of words to see if a duplicate exists before "renaming" the input.

nielsbot Over a year ago

Ok I take it back. I wrote a one pass solution just for fun.

nielsbot Over a year ago

I tried to make something fast--but I'm sure others here will have some performance feedback.

|

Dave DeLong · Accepted Answer · 2013-08-25 04:59:26Z

NSCountedSet is definitely the way to go. You can do it in a single pass if you use two of them: one to know how many there are total, and one to track how many you've seen so far:

NSArray *a = @[@"Hello", @"World", @"Hello"];
NSCountedSet *counts = [NSCountedSet setWithArray:a];

NSMutableArray *final = [NSMutableArray array];
NSCountedSet *countsSoFar = [NSCountedSet set];

for (NSString *str in a) {
    if ([counts countForObject:str] > 1) {
        // this object appears more than once.  append the number of times it's appeared so far
        [countsSoFar addObject:str];
        NSUInteger countSoFar = [countsSoFar countForObject:str];
        str = [str stringByAppendingFormat:@"(%ld)", countSoFar];
    }
    [final addObject:str];
}

NSLog(@"%@", final);

This logs:

(
  "Hello(1)",
  World,
  "Hello(2)"
)

Collectives™ on Stack Overflow

ObjC: count of each string in an array?

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related