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

Question

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

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

我的第一个想法是对数组进行排序，然后再次遍历数组以找到连续序列中断的位置，但排序需要的不仅仅是 O(n)。

任何想法，将不胜感激！

标签： arraysalgorithmbig-o

Answer 1

我的尝试：

该数组A假定为 1-indexed。我们称一个非零且不超过的活动n值。

• 扫描数组，直到找到一个活动值，让A[i] = k（如果找不到，停止）；

• A[k]活动时，

  • 清除时移动A[k]到；kA[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]