查找未在整数集合中使用的第一个整数

Question

在mysql数据库中检索用于ID的整数列表之后,在每种情况下都认为所有ID都不会相互跟随(例如列表可能是[1,2,3,5,10,11,12, 20,...]),除了遍历所有整数之外,找到列表中尚未存在的最小整数(在我们的例子中,它将是4,然后是6),这将是一种更有效的方法4归因于).它也不应该高于999.

这个问题提供了一个mysql查询,但是我想在我的php脚本中执行它,除非它更高效.

Answer 1

使用二进制搜索(以O(log n)运行,比线性搜索更快,即O(n)),可以轻松有效地解决此问题.基本思想是,当且仅当所有数字都存在于某个索引时,则列出[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.

我希望这有帮助!

upd: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;
}