Нахождение самого низкого неиспользованного уникального идентификатора в списке
Скажите, что существует список. Каждый объект в списке имеет уникальный идентификатор.
List [5, 2, 4, 3, 1]
Когда я удаляю объект из этого списка, уникальный идентификатор от объекта идет с ним.
List [5, 2, 3, 1]
Теперь скажите, что я хочу добавить другой объект к списку и дать ему наименее самый низкий уникальный идентификатор.
Что самый легкий путь состоит в том, чтобы получить самый низкий уникальный идентификатор при добавлении нового объекта к списку?
Вот ограничение хотя: я предпочел бы его, если бы я не повторно присваивал уникальный идентификатор другого объекта при удалении объекта.
Я понимаю, что было бы легко найти уникальный идентификатор, если бы я повторно присвоил уникальный идентификатор 5 уникальному идентификатору 4, когда я удалил 4. Затем я мог получить длину списка (5) и создание нового объекта с уникальным идентификатором с тем числом.
Так есть ли иначе, который не включает итерацию через весь список?
Править:
Языком является Java, но я предполагаю, что ищу универсальный алгоритм.
6 ответов
Простой и быстрый способ - просто поместить удаленные идентификаторы в приоритетную очередь и просто выбрать следующий идентификатор оттуда, когда вы вставляете новые (или используйте size () + 1 из первых list как id, когда очередь пуста). Однако для этого потребуется другой список.
Вы можете вести список доступных идентификаторов.
Объявить логический массив (псевдокод):
boolean register[3];
register[0] = false;
register[1] = false;
register[2] = false;
Когда вы добавляете элемент, выполняйте цикл снизу регистра, пока не будет найдено значение false . Установите значение false в значение true, назначьте этот индекс в качестве уникального идентификатора.
removeObject(index)
{
register[index] = false;
}
getsetLowestIndex()
{
for(i=0; i<register.size;i++)
{
if(register[i]==false)
{
register[i] = true;
return i;
}
}
// Array is full, increment register size
register.size = register.size + 1;
register[register.size] = true;
return register.size;
}
Когда вы удаляете элемент, просто установите для индекса значение false.
Вы можете оптимизировать это для больших списков, имея маркеры непрерывности, чтобы вам не нужно было зацикливать все это.
Это лучше всего подойдет для вашего примера, где индексы не расположены в определенном порядке, поэтому вам не нужно сначала сортировать их.
Это эквивалентно поиску, только на этот раз вы ищете недостающее число. Если ваши идентификаторы - отсортированные целые числа, вы можете начать поиск снизу вверх, проверяя, равен ли пробел между двумя идентификаторами 1. Если вы знаете, сколько элементов в списке и как он отсортирован, вы можете реализовать бинарный поиск.
Я не думаю, что вы можете сделать это без итерации по списку.
Когда вы говорите
"Теперь, скажем, я хочу добавить еще один элемент в список, и дать ему наименьший наивысший уникальный идентификатор. '
Я предполагаю, что вы имеете в виду, что хотите присвоить наименьший доступный идентификатор, который не был использован в другом месте.
Вы можете сделать так:
private int GetLowestFreeID(List list){
for (int idx = 0; idx < list.Length; ++i){
if ( list[idx] == idx ) continue;
else return idx;
}
}
this возвращает наименьший свободный индекс.
Это предполагает, что ваш список отсортирован, и это на C#, но вы поняли идею.
Структура данных, которая будет использоваться для этого, представляет собой приоритетную двоичную кучу, которая допускает только уникальные значения.
Как насчет того, чтобы держать список отсортированным. и тогда вы сможете легко удалить его с одного конца.