在一组整数中找到第一个未使用的整数

Question

在从mysql数据库检索用于ID的整数列表后，考虑到在每种情况下并不是所有ID都彼此跟随（例如，列表可以是[1,2,3,5,10,11,12,20，...]），除了循环遍历所有整数以查找尚未在列表中的最低整数之外，还有什么更有效的方法（在我们的例子中，它将是4，然后是6一旦4被指定）。同时它不应该超过999。这个问题 给出了一个mysql查询，但我想在我的php脚本中执行它，除非它更有效率。

- Eldros

---

为什么你需要找到这些数字？ - sapht

@sapht：我的数据库条目是通过ID和类别唯一定义的，这意味着一个ID可以被使用两次，但不能在同一类别中使用。我参与了一个历史悠久的项目，其中有一段时间ID不是按顺序分配的，而是手动分配的。现在工具需要自动生成ID，我通常会取最高的ID并加上1。但我们面临的问题是ID的限制不能超过999。 - Eldros

Answer 1

这个问题可以很容易、高效地使用二分查找（时间复杂度为O(log n)，比线性查找的O(n)更快）来解决。基本思路是，只有当所有数字到达某个索引时，list[index] = index + 1 (例如，list[0] = 1，list[1] = 2 等)。这一特性可用于确定缺失的最小数字在列表的某个元素之前还是之后，从而进行二分查找。

实现很简单（我不会PHP，所以这里是伪代码）。

lower_bound = 0
upper_bound = length(list) - 1
index = floor((lower_bound + upper_bound) / 2)
while (lower_bound != upper_bound)  
     if(list[index] = index + 1)     // missing number is after index
          lower_bound = index + 1
          index = floor((lower_bound + upper_bound) / 2)
     else                            // missing number is at or before index
          upper_bound = index
          index = floor((lower_bound + upper_bound) / 2)
missing_number = upper_bound + 1     // add 1 because upper_bound is the index

missing_number将是最小的缺失数字，如果没有缺失数字，则为length(list) + 1。

---

或者使用递归，听说效率较低。

first_missing_number(list, lower_bound, upper_bound) {
     if(lower_bound = upper_bound)  // found the first missing number
          return upper_bound + 1    // add 1 because upper_bound is the index
     index = floor((lower_bound + upper_bound) / 2)
     if (list[index] = index + 1)   // missing number is after index
          first_missing_number(list, index + 1, upper_bound)
     else                           // missing number is at or before index
          first_missing_number(list, lower_bound, index)
}

如果列表中有数字缺失，first_missing_number（list，0，length（list）-1）将返回第一个缺失的数字。如果没有数字缺失，则返回length（list）+ 1。希望这可以帮到您！更新：PHP版本。

function first_free($list) {
    $lwr = 0;
    $upr = count($list);

    while ($lwr < $upr) { 
        $m = ($lwr + $upr) >> 1;
        if($list[$m] == $m + 1)
            $lwr = $m + 1;
        else
            $upr = $m;
    }
    return $upr + 1;
}

- smackcrane

---

真他妈的简单，上次我遇到这个问题时，最后用了一个哈希表+索引树。现在感觉自己像个傻瓜。好棒的解决方案！ - kyun

Answer 2

最有效的方法是使用简单循环：

foreach($list as $n => $v)
   if($v !== $n + 1) return $n + 1;

- user187291

---

随着服务器负载等因素的影响，这种方法会变得非常低效。当然，如果需要迭代数万个或更多的键，则情况会更糟，但最好由MySQL中的本地代码处理，而不是每次获取脚本时通过PHP进行解释。 - gnxtech3

Answer 3

你可以使用 array_diff() 函数：

例如：

<?php
$array1 = array("a" => "1", "2", "3", "4");
$array2 = array("b" => "2", "4");
$result = array_diff($array1, $array2);

print_r($result);
?>

这将会给你第二个数组中缺失的项：

Array
(
    [1] => 1
    [2] => 3
)

- Sujit Agarwal

Answer 4

也许这将是更有效的方法：

$your_list = array(....);
$number_you_want = min(array_diff(range(1,999), $your_list));

- Teneff

Answer 5

由于您仅限于999个可能的键，我可能会创建一个临时表，其中包含所有可能的键（即1-999），甚至为此目的创建一个永久表，然后您可以执行以下SQL语句：

SELECT key_value FROM temp_key_table WHERE key_value NOT IN (SELECT key FROM original_table ORDER BY key ASC) ORDER BY key_value ASC LIMIT 1

不确定这有多实用，SQL大师可能能给你更好的解决方案，但这应该是一个临时解决办法，而不是在PHP中搞这个。

- gnxtech3

Answer 6

$array   = array(1,2,3,5,10,11,12,20);
$missing = array_diff(range(min($array), max($array)), $array);

// First missing number is at $missing[0], next at $missing[1], etc.

- salathe

---

@discipulus，你错了。如果缺少或其他情况下没有1，它也可以正常工作。 - salathe

但是，由于range函数的起始值是$ array中的最小值，因此如果$ array中缺少1，则range返回的数组也不会包括1。 因此，array_diff也不会包括1，而实际上1是最小的缺失数字。（我应该补充说明，我的理解是要找到[1..999]中缺失的最小整数）。 - smackcrane