Нахождение наименьшего неиспользованного уникального идентификатора в списке

Question

Скажи, что есть список.Каждый элемент в списке имеет уникальный идентификатор.

List [5, 2, 4, 3, 1]

Когда я удаляю элемент из этого списка, уникальный идентификатор из элемента идет вместе с ним.

List [5, 2, 3, 1]

Теперь скажите, что я хочу добавить еще один элемент в список и присвоить ему наименьший уникальный идентификатор.

Какой самый простой способ получить наименьший уникальный идентификатор при добавлении нового элемента в список?

Однако есть ограничение: я бы предпочел, чтобы я не переназначил уникальный идентификатордругого элемента при удалении элемента.

Я понимаю, что было бы легко найти уникальный идентификатор, если бы я переназначил уникальный идентификатор 5 уникальному идентификатору 4, когда я удалил 4. Затем я мог бы получить длину списка (5) и создать новый элемент суникальный идентификатор с этим номером.

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

РЕДАКТИРОВАТЬ:

Язык Java, но я думаю, что я ищууниверсальный алгоритм.

Answer 1

Простой и быстрый способ - просто поместить удаленные идентификаторы в очередь с приоритетами и просто выбрать следующий идентификатор при вставке новых (или использовать size () + 1 из первого списка в качестве идентификатора, когда очередьпусто).Однако для этого потребуется другой список.

Answer 2

Вы могли бы поддерживать список доступных идентификаторов.

Объявите логический массив (псевдокод):

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.

Вы можете оптимизировать это для больших списков.имея маркеры непрерывности, чтобы вам не нужно было зацикливать все это.

Это лучше всего подойдет для вашего примера, когда индексы расположены не в определенном порядке, поэтому вы сначала пропускаете их сортировку.

Answer 3

Как насчет сохранения списка отсортированным. и чем вы можете легко снять его с одного конца.

Answer 4

Структура данных, которая будет использоваться для этого, является Приоритетной двоичной кучей, которая допускает только уникальные значения.

Answer 5

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

Когда вы говорите

'Теперь скажите, что я хочу добавить еще один элемент в список, идайте ему наименее высокий уникальный идентификатор.'

Я предполагаю, что вы хотите назначить наименьший из доступных идентификаторов, который не использовался в других местах.

Вы можете сделать это:

private int GetLowestFreeID(List list){
    for (int idx = 0; idx < list.Length; ++i){
        if ( list[idx] == idx ) continue;
        else return idx;
    }
}

thisвозвращает наименьший свободный индекс.

Предполагается, что ваш список отсортирован и находится на C #, но вы поняли идею.

Answer 6

Это эквивалентно поиску, только в этот раз вы ищете пропущенное число. Если ваши идентификаторы отсортированы целыми числами, вы можете начать идти снизу вверх, проверяя, равен ли интервал между двумя идентификаторами 1. Если вы знаете, сколько элементов в списке и как они отсортированы, вы можете выполнить бинарный поиск.