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

Question

У меня есть массив, содержащий имена элементов. Я хочу дать пользователю возможность создавать элементы без указания их имени, поэтому моя программа должна будет предоставить уникальное имя по умолчанию, например «Item 1».

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

Очевидное решение будет что-то вроде этого:

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

Моя проблема с этим алгоритмом, что он работает в O (N^2).

Интересно, существует ли известный (или новый) более эффективный алгоритм для решения этого случая.

Другими словами, мой вопрос заключается в следующем: существует ли какой-либо алгоритм, который найдет первое большее, чем нулевое число, которое доза НЕ существует в данном массиве и работает меньше, чем N^2?

Answer 1

Вы, конечно, можете сделать это в O (N) времени, N-число элементов в массиве:

• Один из "пункта 1", "Пункт 2", ... «Пункт N +1 "должно быть бесплатным, поэтому создайте массив из N + 1 флагов.
• Пройдите по пунктам, и для каждого имени, если оно имеет форму «Item k» с 0 < k < = N + 1, установите этот флаг.
• Сканирование массива флагов для первого четкого флага.

Дополнительное требование к памяти - это 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

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

Answer 4

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

Answer 5

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

первый:

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

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

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

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

Answer 6

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

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

Answer 7

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

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

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