将最小可能的正整数插入唯一整数数组

Question

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

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

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

任何想法，将不胜感激！

Answer 1

我的尝试：

该数组A假定为1索引。我们称之为积极的价值一个是非零和不超过n。

• 扫描数组，直到找到一个有效值，然后让它继续A[i] = k（如果找不到，停止）；

• 在A[k]活动期间，

  • 移动A[k]到k同时结算A[k];

• 从继续i直到到达阵列的末尾。

此遍之后，将清除与数组中某个整数对应的所有数组条目。

• 查找第一个非零条目，并报告其索引。

例如

[5, 3, 2, 7], clear A[3]
[5, 3, 0, 7], clear A[2]
[5, 0, 0, 7], done

答案是1。

例如

[5, 3, 2, 7, 1], clear A[5],
[5, 3, 2, 7, 0], clear A[1]
[0, 3, 2, 7, 0], clear A[3],
[0, 3, 0, 7, 0], clear A[2],
[0, 0, 0, 7, 0], done

答案是4。

第一遍的行为是线性的，因为每个数字都被同时查看（并立即清除），并且有i规律地增加。

第二遍是线性搜索。

A= [5, 3, 2, 7, 1]
N= len(A)

print(A)
for i in range(N):
    k= A[i]
    while k > 0 and k <= N:
        A[k-1], k = 0, A[k-1] # -1 for 0-based indexing
        print(A)

[5, 3, 2, 7, 1]
[5, 3, 2, 7, 0]
[0, 3, 2, 7, 0]
[0, 3, 2, 7, 0]
[0, 3, 0, 7, 0]
[0, 0, 0, 7, 0]
[0, 0, 0, 7, 0]

更新：

基于 ？？？？????的想法，我们可以以不破坏值的方式标记数组元素。然后，您报告第一个未标记的索引。

print(A)
for a in A:
    a= abs(a)
    if a <= N:
        A[a-1]= - A[a-1] # -1 for 0-based indexing
    print(A)

[5, 3, 2, 7, 1]
[5, 3, 2, 7, -1]
[5, 3, -2, 7, -1]
[5, -3, -2, 7, -1]
[5, -3, -2, 7, -1]
[-5, -3, -2, 7, -1]

Answer 2

从问题描述来看：“允许将数组中的值分配给其他整数。” 这是 O(n) 空间，不是常数。

循环数组并乘以A[ |A[i]| - 1 ]-1 for |A[i]| < array length。第二次循环并输出第一个非负单元格的（索引 + 1），或者如果它们都被标记，则输出（数组长度 + 1）。这利用了数组中不能超过（数组长度）个唯一整数的事实。