高效的算法来找到第一个可用的名字 [英] Efficient algorithm to find first available name

问题描述

我有一个包含项目名称的数组。 我想给用户创造的物品，而无需指定他们的名字，所以我的程序必须提供一个唯一的默认名称，如项目1的选项。

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".

目前的挑战是，这个名字必须是唯一的，所以我必须检查所有的数组的默认名称，如果有一个项目具有相同的名称，我必须将名称更改为项目2等直到我找到一个可用的名称。

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 = "Item ";
for (int i = 0; !isAvailable(name + i) ; i++);

我的问题与算法，它运行在O（N ^ 2）。

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.

在换句话说我的问题是：是否有任何的算法，发现剂量定数组不存在的第一个大于零的数字，并运行在不到N ^ 2

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?

推荐答案

您当然可以做到这一点在O（n）时间，N为您的阵列中的项目数：

You can certainly do it in O(N) time, N being the number of items in your array:

• 在一个项目1，项目2，......项N + 1必须是免费的，所以创建N + 1标志的数组。
• 遍历中的项目，并且对于每个名称，如果它是形式项K与0℃ K＆LT; = N + 1，设置标志
• 扫描标志数组的第一个明确的标志。

附加内存要求是N + 1位，这当然比任何数据结构的实际存储所有的N个名字。

Additional memory requirement is N+1 bits, which certainly beats any data structure that actually stores all N names.

这篇关于高效的算法来找到第一个可用的名字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！