Efficient algorithm to find first available name
Posted
by
Avrahamshuk
on Stack Overflow
See other posts from Stack Overflow
or by Avrahamshuk
Published on 2011-01-14T21:41:15Z
Indexed on
2011/01/14
21:53 UTC
Read the original article
Hit count: 371
I have an array containing names of items. I want to give the user the option to create items without specifying their name, so my program will have to supply a unique default name, like "Item 1".
The challenge is that the name has to be unique so i have to check all the array for that default name, and if there is an item with the same name i have to change the name to be "Item 2" and so on until i find an available name.
The obvious solution will be something like that:
String name;
for (int i = 0 , name = "Item " + i ; !isAvailable(name) ; i++);
My problem with that algorithm is that it runs at O(N^2).
I wonder if there is a known (or new) more efficient algorithm to solve this case.
In other words my question is this: Is there any algorithm that finds the first greater-than-zero number that dose NOT exist in a given array, and runs at less that N^2?
Thanks!
© Stack Overflow or respective owner