Geek Answers Handbook

Effective algorithm for finding the first available name

I have an array containing element names. I want to give the user the ability to create items without specifying their name, so my program will have to provide a unique name by default, for example "Item 1".

The problem is that the name must be unique, so I have to check the whole array for this name by default, and if there is an element with the same name, I have to change the name as "Item 2" and so on until I find an available name.

The obvious solution would be:

String name = "Item ";
for (int i = 0; !isAvailable(name + i) ; i++);

My problem with this algorithm is that it works in O (N ^ 2).

I wonder if there is a well-known (or new) more efficient algorithm for solving this case.

In other words, my question is this: is there any algorithm that finds the first greater number, nonzero, which does not exist in this array, and works with less than N ^ 2?

+5
source share
7 answers

You can do this O (N) times, N is the number of elements in your array:

  • One of "Item 1", "Item 2", ... "Item N + 1" should be free, so create an array of N + 1 flags.
  • Move items and for each name, if it has the form "Item k" with 0 <k <= N + 1, set this flag.
  • Scanning an array of flags for the first clarity flag.

- N + 1 , , , , N .

+4

, .

. , ( 1). O (n log n), O (n), O (n log n).

-, O (n) O (1) . , O (n) .

, O (n) , - "" , -. ( , O (n)).

+3

, , ?

+1

-. , isAvailable, -. , O (nh), h - .

+1

:

:

  • , N
  • , ( ++: std:: map), (N)

, "N x log (N)"

, , "", . - N.

, - N x log (N) + N : N log (N).

+1

, nanoseconds? , , , , , , -, .

, O (1) .

0

Logarithmic approach, assuming you never leave holes by removing elements:

// Inverse binary search for the last one.
int upperBound = 1;
while(isInUse(upperBound)) upperBound *= 2;

// Standard binary search for the end once we have a ballpark.
int lowerBound = upperBound / 2;
while(lowerBound < upperBound - 1)
{
    int midpoint = (lowerBound + upperBound) / 2;
    if (isInUse(midpoint))
        lowerBound = midpoint;
    else
        upperBound = midpoint;
}
return upperBound;

If item numbers can be freed by deletion, nothing but a linear search will work unless you also save the "free list" and select from it.

0
source

More articles:


All Articles