有趣的搜索问题：查找不在列表中的值（每日编码问题，2020年5月26日）

Question

我想知道是否有人愿意从“每日编码问题”电子邮件列表中就我对今天问题的解决方案提供一些反馈。关于查找列表中不存在的第一个值，而不是查找其中存在的值，这是一个有趣的问题。

此问题由Stripe提出。

给出整数数组，找到线性时间中的第一个缺失的正整数，然后恒定的空间。换句话说，找到数组中不存在的最低正整数。数组也可以包含重复项和负数。

例如，输入[3，4，-1，1]应该给出2。输入[1,2，0]应该给出3。

您可以就地修改输入数组。

我的主要问题是，我不确定我是否满足O（n）时间和O（1）空间要求。这是我使用Groovy的解决方案：

def find_first( Xs ) {
  ys = []
  szXs = Xs.size()
  // First, transfer Xs list to a set ys.
  szXs.times { // this loop is O(n)
    if ( (hd = Xs.head()) > 0 ) { ys << hd; } // We only need to keep val if it's positive.
    Xs = Xs.drop(1); // Remove val from Xs in order to meet O(1) space requirement.
  }
  ys = ys.toSet() // converting list to set is O(n)
  sz = ys.size()  // ys.size() might be same as Xs.size(), but it could be smaller, so give it a new var.
  for (int i = 1; i < sz; ++i) { // this loop is O(n)
    if ( !ys.contains(i) ) return i // Testing a hash set for set membership is O(1)
  }
  return sz + 1 // if this point is reached, ys had all values [1..sz] already
} // end find_first

def test(Xs) {
  println "\nstarting with Xs = " + Xs
  ans1 = find_first( Xs )
  println "first missing = " + ans1
}

xs1 = [ 3,4,-1,1 ]
xs2 = [ 1, 2, 0 ]
xs3 = [ 7, 8 ]
xs4 = [ 1,1,2,1 ]
xs5 = [ -4, -1 ]

test(xs1)
test(xs2)
test(xs3)
test(xs4)

test（xs5）

这是输出：

以Xs开头= [3，4，-1，1]第一次失踪= 2

以Xs开头= [1、2、0]第一次失踪= 3

以Xs开头= [7，8]第一次失踪= 1

以Xs开头= [1，1，2，1]第一次失踪= 3

以Xs开头= [-4，-1]第一次失踪= 1

---

因此，在有限的一组值上是正确的，只想确保它是O（n）时间和O（1）空间。任何建议表示赞赏！汉克

Answer 1

我不熟悉groovy，但是似乎您的代码是O(n)空间，因为您创建了一个额外的哈希集（ys）。

请注意，该问题带有提示：

您可以就地修改输入数组。

这可以在O(n)时间中用O（1）空间完成，方法是先用radix sort对数组进行就地排序，然后遍历值以查找第一个缺失的值。