Уникальный алгоритм массива с увеличивающимися дубликатами

Question

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

Начать с массива [1 5 3 4 6] и вставлять 3.
Последовательность должна быть:

[1 5 3 4 6 ] - толчок 3
[1 5 4 6 3] - приращение от 3 до 4
[1 5 4 6 3] - приращение 4 до 5
[1 4 5 6 3] - приращение от 5 до 6
[1 6 4 5 7 3] - приращение от 6 до 7

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

Answer 1

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

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

def incrementHelper(list, e): 
    if (list.contains(e)): 
     incrementHelper(list, e+1) 
     list.set(list.indexOf(e), e+1) 

def appendAndIncrement(list, e) 
    incrementHelper(list, e) 
    return list.append(e) 

Редактировать: Вы правы, что другое решение не сработает - мое плохое. Это использует рекурсивное решение и должно избегать проблемы, о которой вы говорили.