小编mar*_*nic的帖子

我正在尝试解决这个采访问题：给定一个唯一的正整数数组，找到要插入其中的最小数，以便每个整数仍然是唯一的。该算法应为O（n），并且额外的空间复杂度应为常数。允许将数组中的值分配给其他整数。

例如，对于array [5, 3, 2, 7]，输出应为1。但是对于[5, 3, 2, 7, 1]，答案应为4。

我的第一个想法是对数组进行排序，然后再次遍历该数组以查找连续序列的中断点，但是排序需要的比O（n）还多。

任何想法，将不胜感激！