На самом деле, если максимальное количество значений бесконечно, вы можете использовать любой алгоритм сжатия без потерь для монохромного растрового изображения. Если вы представляете квадрат с как минимум количеством пикселей, равным количеству возможных значений, вы можете отобразить каждое значение на пиксель (с несколькими запасными). Затем вы можете представить белый цвет как появившиеся пиксели и черный для остальных и использовать любой алгоритм сжатия, если пространство имеет большую цену (это, безусловно, проблема, которая была изучена)
Вы также можете хранить блоки. Наихудший случай такой же в пространстве O (n), но для этого наихудшего случая вам нужно, чтобы появившееся число имело ровно 1 между ними. Как только появятся новые цифры, память уменьшится:
Я напишу псевдокод, и я буду использовать список, но вы всегда можете использовать другую структуру
List changes // global
boolean addNumber(int number):
boolean appeared = false
it = changes.begin()
while it.hasNext():
if it.get() < number:
appeared != appeared
it = it.next()
else if it.get() == number:
if !appeared: return true
if it.next().get() == number + 1
it.next().remove() // Join 2 blocks
else
it.insertAfter(number + 1) // Insert split and create 2 blocks
it.remove()
return false
else: // it.get() > number
if appeared: return true
it.insertBefore(number)
if it.get() == number + 1:
it.remove() // Extend next block
else:
it.insertBefore(number + 1)
}
return false
}
Что этот код следующий: он хранит список блоков. Для каждого добавляемого вами числа он перебирает список, в котором хранятся блоки с номерами, которые появились, и номера, которые не были. Позвольте мне проиллюстрировать это на примере; Я добавлю [), чтобы проиллюстрировать, какие числа в блоке, первое число включено, последнее нет. В псевдокоде оно заменяется логическим appeared. Например, если вы получите 5, 9, 6, 8, 7 (в этом порядке), у вас будут следующие последовательности после каждой функции:
[5,6)
[5,6), [9,10)
[5,7), [9,10)
[5,7), [8,10)
[5,10)
В последнем значении вы сохраняете блок из 5 чисел только с 2.