Эффективный алгоритм поиска первого доступного имени

Question

У меня есть массив, содержащий имена предметов.Я хочу дать пользователю возможность создавать элементы без указания их имени, поэтому моя программа должна будет предоставить уникальное имя по умолчанию, например «Элемент 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», ... »Элемент N + 1 "должен быть свободным, поэтому создайте массив из N + 1 флагов.
• Обходите элементы и для каждого имени, если оно имеет форму" Элемент k "с 0
• Сканируйте массив флагов для первого флага очистки.

Требуется дополнительное количество памяти N + 1 бит, что, безусловно, превосходит любую структуру данных, которая фактически хранит всеN имен.

Answer 2

Да, есть.

Сначала отсортируйте массив. Затем выполните его и верните первый элемент, значение которого не равно его индексу (плюс 1). Сортировка O (n log n), последний шаг O (n), так что все дело в O (n log n).

Если вы поместите все элементы в хеш-таблицу, вы можете сделать это за O (n) за счет некоторого места и дополнительного шага O (1) при создании новых элементов. Поскольку каждый элемент должен быть посещен, O (n) явно оптимально.

Мне было бы интересно посмотреть, есть ли O (n) способ сделать это, без , использующий любую «постоянную» структуру данных, такую ​​как хеш-таблица (И при условии неограниченных целых чисел, в противном случае сортировка сегментов могла бы использоваться в качестве алгоритма сортировки O (n)).

Answer 3

Вы можете попробовать сделать следующее:

первый:

• цикл по списку, и получить все пронумерованные элементы, это сложность N
• для каждого пронумерованного элемента поместите элемент в дерево (в C ++: std :: map), это журнал сложности (N)

Итак, теперь вы создали карту с использованными числами, со сложностью «N x log (N)»

Далее, перейдите к дереву и, как только вы увидите «дыру», используйте номер. Наихудший случай - сложность N.

Таким образом, в целом сложность составляет N x log (N) + N или упрощенно: N log (N).

Answer 4

Вставьте все существующие имена в хеш-таблицу.Повторите ваш цикл, но сделайте isAvailable, проверьте хеш-таблицу.Предполагая приличный хеш, это O (nh), где h - стоимость оценки хеша.

Answer 5

Почему бы просто не отслеживать максимальное число на сегодняшний день, а когда вам нужно новое, увеличить его?

Answer 6

Логарифмический подход, предполагающий, что вы никогда не оставляете «дыры», удаляя элементы:

// 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;

Если номера элементов можно освободить путем удаления, ничего, кроме линейного поиска, не будет работать, если только вы не сохраните «свободный список» и не выберете его.

Answer 7

Если к этому массиву будет доступ только один пользователь, почему бы не использовать число наносекунд ?Это, конечно, предполагает, что пользователь на намного медленнее компьютера, что кажется безопасным предположением.

Таким образом, у вас есть O (1) стоимость для определенияуникальное имя.