Ruby：在ID数组中查找最低的空闲ID

Question

我有一个数组，其包含从1到4000不同的ID。我需要向数据库中添加一些具有相应ID的元素。由于最大可能的ID是4000（在我的情况下并不多），我希望能够找到可用于新元素的最低未使用ID。

在C ++中，我会编写一个循环，在其中检查array [i] == array [i + 1] - 1。如果不是这种情况，则新ID将为array [i] + 1。

我对如何在Ruby中编写此代码毫无头绪。

- Cocotton

---

这会导致id 1在一月份指向苹果，但在二月份可能指向香蕉。正常的做法是让数据库管理id列。你最多只有4000个id，这使得它们看起来像是有意义的（比如0-4000是食品类别，4001-5000是玩具类别）——这是一个糟糕的想法。 - steenslag

Answer 1

使用范围（range）可以找到第一个不属于你的数组的元素：

array = [1,2,3,5,6]
(1..4000).find { |i| !array.include?(i) }
# => 4

- Dylan Markow

---

这可能非常低效，因为include?方法可能会被调用成千上万次（它的复杂度是二次的）。 - Marek Příhoda

是的，当第一个可用id变高时（当它为3999时），确实会出现一些缓慢。其他答案已经解决了这个问题。 - Dylan Markow

Answer 2

array = [1, 2, 3, 5, 6]
(1..4000).to_a.-(array).min

- sawa

---

+1 @sawa，非常好和简洁。应该也会运行得非常快。 - the Tin Man

这确实非常聪明。 - Marek Příhoda

我使用了这个，它完美地工作了，非常感谢你的帮助！ - Cocotton

Answer 3

def first_unused_id(ids)
  index = ids.each_index.find{|i| ids[i] + 1 != ids[i+1] }
  ids[index] + 1
end

一些解释:

• each_index方法会将数组转换为一个枚举器对象，该对象包含数组的索引。
• find方法会返回第一个从传递给它的块中得到true结果的元素。

- Jakub Hampl

Answer 4

这个怎么样：

(1..4000).find { |i| array[i-1] != i }

类似于Dylan的答案，但在这种情况下，它只是检查数组的第[n-1]个成员是否为n。如果不是，则该索引是“开放”的，并返回。此解决方案每个索引只需要一次检查，而不是4000次...

array = [1,2,3,5,6]

这将找到数组 [4-1] != 4（因为数组[3]=5），并返回4作为第一个可用的ID。

（这需要一个已排序的索引数组，但目前为止已经假定了这一点）

- elijah

---

这会有一个偏差 -- array[0] 应该是 1 而不是 0；应该是 array[i-1]。另外，你发布的代码根本无法工作，因为 !array[i] 总是 false。应该是 array[i-1] != i。 - Dylan Markow

Answer 5

array = [1, 2, 3, 5, 6]

def lowest_unused(ids)
  ids.find { |e| ids.index(e) + 1 != e } - 1
end

p lowest_unused(array) # 4

- Marek Příhoda

---

类似Jakub Hampl的答案，但更简单一些。 - Marek Příhoda