查找第一个可用名称的高效算法

Question

我有一个包含项目名称的数组.我想让用户选择创建项目而不指定其名称,因此我的程序必须提供唯一的默认名称,如"Item 1".

挑战是名称必须是唯一的,所以我必须检查所有数组的默认名称,如果有一个具有相同名称的项目,我必须将名称更改为"项目2",依此类推,直到我找到可用的名称.

显而易见的解决方案是这样的:

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

我的算法问题是它运行在O(N ^ 2).

我想知道是否有一种已知的(或新的)更有效的算法来解决这种情况.

换句话说,我的问题是:是否有任何算法可以找到在给定数组中不存在的第一个大于零的数字,并且运行的数量少于N ^ 2？

Answer 1

您当然可以在 O(N) 时间内完成此操作，N 是数组中的项目数：

• “Item 1”、“Item 2”、...“Item N+1”之一必须是空闲的，因此创建一个包含 N+1 标志的数组。
• 遍历项目，对于每个名称，如果它的形式为“Item k”且 0 < k <= N+1，则设置该标志。
• 扫描标志数组以查找第一个清除标志。

额外的内存需求是 N+1 位，这肯定胜过任何实际存储所有 N 个名称的数据结构。