arrays - 具有递增重复项的独特数组算法

Question

在设计算法来满足此需求方面需要帮助。起始输入将是已知包含唯一整数的数组。不一定有序或连续，可以是正数或负数。需要将一个新整数推送到数组并通过递增冲突项目来保持项目的唯一性。不过，它们出现的顺序应该保留。例如:

从数组 [1 5 3 4 6] 开始并插入 3。
顺序应该是:

[1 5 3 4 6 3] - push 3
[1 5 4 4 6 3] - increment 3 to 4
[1 5 4 5 6 3] - increment 4 to 5
[1 6 4 5 6 3] - increment 5 to 6
[1 6 4 5 7 3] - increment 6 to 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)

编辑:你是对的，其他解决方案行不通 - 我的错。这个使用递归解决方案，应该可以避免您提到的问题。