时间戳

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

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

问题描述

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

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)

测试（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) 空间。任何建议表示赞赏！汉克

标签： algorithmgroovybig-o

解决方案

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

请注意，这个问题有一个提示：

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

这可以在O(n)O(1) 空间内及时完成，方法是首先使用radix sort对数组进行就地排序，然后遍历这些值以找到第一个丢失的值。

推荐阅读