我有一个整数范围，可能会也可能不会缺少一些数字。是否可以在不使用循环结构的情况下找到最小的缺失数字？如果没有缺少的数字，则该函数应返回范围的最大值加一。
这就是我使用 for 循环解决它的方式：
$range = [0,1,2,3,4,6,7];
// sort just in case the range is not in order
asort($range);
$range = array_values($range);
$first = true;
for ($x = 0; $x < count($range); $x++)
{
// don't check the first element
if ( ! $first )
{
if ( $range[$x - 1] + 1 !== $range[$x])
{
echo $range[$x - 1] + 1;
break;
}
}
// if we're on the last element, there are no missing numbers
if ($x + 1 === count($range))
{
echo $range[$x] + 1;
}
$first = false;
}
理想情况下，我想完全避免循环，因为范围可能很大。有什么建议吗？
算法解决方案
有一种方法可以使用算法检查是否缺少数字。这里解释过。基本上，如果我们需要将数字从 1 加到 100。我们不需要通过对它们求和来计算，我们只需要执行以下操作：(100 * (100 + 1)) / 2 .那么这将如何解决我们的问题呢？
我们将得到数组的第一个元素和最后一个元素。我们用这个算法计算总和。然后我们使用array_sum()来计算实际总和。如果结果相同，则没有遗漏的数字。然后，我们可以通过从计算中减去实际总和来"回溯"缺失的数字。当然，这仅在仅缺少一个数字时才有效，如果缺少多个数字，则会失败。因此，让我们将其放入代码中：
$range = range(0,7); // Creating an array
echo check($range) . "'r'n"; // check
unset($range[3]); // unset offset 3
echo check($range); // check
function check($array){
if($array[0] == 0){
unset($array[0]); // get ride of the zero
}
sort($array); // sorting
$first = reset($array); // get the first value
$last = end($array); // get the last value
$sum = ($last * ($first + $last)) / 2; // the algo
$actual_sum = array_sum($array); // the actual sum
if($sum == $actual_sum){
return $last + 1; // no missing number
}else{
return $sum - $actual_sum; // missing number
}
}
输出
8
3
在线演示
如果缺少几个数字，则只需使用array_map()或类似的东西来执行内部循环。
正则表达式解决方案
让我们将其提升到一个新的水平并使用正则表达式！我知道这是无稽之谈，不应该在现实世界中使用它。目标是展示正则表达式的真正力量:)
因此，首先让我们使用以下格式创建一个超出我们范围的字符串：I,II,III,IIII 表示范围1,3。
$range = range(0,7);
if($range[0] === 0){ // get ride of 0
unset($range[0]);
}
$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
echo $str;
输出应如下所示：I,II,III,IIII,IIIII,IIIIII,IIIIIII .
我想出了以下正则表达式：^(?=(I+))(^'1|,'2I|'2I)+$ .这是什么意思呢？
^ # match begin of string
(?= # positive lookahead, we use this to not "eat" the match
(I+) # match I one or more times and put it in group 1
) # end of lookahead
( # start matching group 2
^'1 # match begin of string followed by what's matched in group 1
| # or
,'2I # match a comma, with what's matched in group 2 (recursive !) and an I
| # or
'2I # match what's matched in group 2 and an I
)+ # repeat one or more times
$ # match end of line
让我们看看实际发生了什么....
I,II,III,IIII,IIIII,IIIIII,IIIIIII
^
(I+) do not eat but match I and put it in group 1
I,II,III,IIII,IIIII,IIIIII,IIIIIII
^
^'1 match what was matched in group 1, which means I gets matched
I,II,III,IIII,IIIII,IIIIII,IIIIIII
^^^ ,'2I match what was matched in group 1 (one I in thise case) and add an I to it
I,II,III,IIII,IIIII,IIIIII,IIIIIII
^^^^ '2I match what was matched previously in group 2 (,II in this case) and add an I to it
I,II,III,IIII,IIIII,IIIIII,IIIIIII
^^^^^ '2I match what was matched previously in group 2 (,III in this case) and add an I to it
We're moving forward since there is a + sign which means match one or more times,
this is actually a recursive regex.
We put the $ to make sure it's the end of string
If the number of I's don't correspond, then the regex will fail.
看到它工作和失败。让我们把它放在PHP代码中：
$range = range(0,7);
if($range[0] === 0){
unset($range[0]);
}
$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
if(preg_match('#^(?=(I*))(^'1|,'2I|'2I)+$#', $str)){
echo 'works !';
}else{
echo 'fails !';
}
现在让我们考虑返回缺少的数字，我们将删除$结束字符以使我们的正则表达式不会失败，我们使用组 2 返回丢失的数字：
$range = range(0,7);
if($range[0] === 0){
unset($range[0]);
}
unset($range[2]); // remove 2
$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
preg_match('#^(?=(I*))(^'1|,'2I|'2I)+#', $str, $m); // REGEEEEEX !!!
$n = strlen($m[2]); //get the length ie the number
$sum = array_sum($range); // array sum
if($n == $sum){
echo $n + 1; // no missing number
}else{
echo $n - 1; // missing number
}
在线演示
编辑：注
这个问题是关于性能的。像array_diff和array_filter这样的功能并不是神奇的快。他们可能会增加巨大的时间损失。将代码中的循环替换为对array_diff的调用不会神奇地使事情变得快速，并且可能会使事情变慢。如果您打算使用这些函数来加快代码速度，则需要了解它们的工作原理。这个答案使用没有重复的项目和不存在无效元素的假设，以允许我们使用元素的位置来推断其期望值。
从理论上讲，如果您从排序列表开始，此答案是最快的解决方案。如果需要排序，杰克发布的解决方案理论上是最快的。
在系列 [0,1,2,3,4,...] 中，如果第 n 个元素前面没有元素丢失，则其值为 n。因此，我们可以随时抽查，以查看我们缺少的元素是在相关元素之前还是之后。
因此，您首先将列表切成两半，并检查位置 x = x 的项目是否
[ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ]
^
是的，list[4] == 4.因此，从列表末尾的当前点移一半。
[ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ]
^
呃，list[6] == 7.因此，在我们上一个检查点和当前检查点之间的某个地方，缺少一个元素。将差分分成两半并检查该元素：
[ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ]
^
在这种情况下，list[5] == 5
所以我们在那里很好。因此，我们将当前检查与上次异常检查之间的距离缩短一半。哦..看起来单元格n+1是我们已经检查过的单元格。我们知道list[6]==7和list[5]==5，所以元素编号6是缺失的。
由于每个步骤都将要考虑的元素数一分为二，因此您知道最坏情况的性能将检查不超过总列表大小的日志2。也就是说，这是一个 O(log(n(( 解决方案。
如果这整个安排看起来很熟悉，那是因为你在大学二年级的计算机科学课上学到了它。这是二叉搜索算法的微小变化 - 这是业内使用最广泛的索引方案之一。事实上，这个问题似乎是这种搜索技术的完美应用。
当然，您可以重复该操作以查找其他缺失的元素，但由于您已经测试了列表中关键元素的值，因此您可以避免重新检查列表的大部分内容，而直接转到剩下的有趣元素进行测试。
另请注意，此解决方案假定列表已排序。如果列表没有排序，那么显然你先排序。除了，二进制搜索与快速排序有一些值得注意的属性。您很有可能将排序过程与查找缺失元素的过程结合起来，并在单个操作中同时执行这两项操作，从而节省一些时间。
最后，总结一下列表，这只是一个愚蠢的数学技巧。从 1 到 N 的数字列表的总和正好是 N*(N+1)/2 .如果您已经确定缺少任何元素，那么只需减去缺少的元素即可。
从技术上讲，你不能真正没有循环(除非你只想知道是否缺少数字(。但是，您无需先对数组进行排序即可完成此操作。
以下算法使用 O(n( 时间和 O(n( 空间：
$range = [0, 1, 2, 3, 4, 6, 7];
$N = count($range);
$temp = str_repeat('0', $N); // assume all values are out of place
foreach ($range as $value) {
if ($value < $N) {
$temp[$value] = 1; // value is in the right place
}
}
// count number of leading ones
echo strspn($temp, '1'), PHP_EOL;
它构建了 N 个条目的有序标识映射，根据其位置将每个值标记为"1";最后所有条目都必须为"1"，第一个"0"条目是缺少的最小值。
顺便说一句，我正在使用临时字符串而不是数组来减少物理内存需求。
老实说，我不明白为什么你不想使用循环。循环没有错。它们很快，你根本离不开它们。但是，在您的情况下，有一种方法可以避免使用 PHP 核心函数编写自己的循环。不过，它们确实会遍历数组，但您根本无法避免这种情况。
无论如何，我收集了你所追求的东西，可以很容易地用 3 行写：
function highestPlus(array $in)
{
$compare = range(min($in), max($in));
$diff = array_diff($compare, $in);
return empty($diff) ? max($in) +1 : $diff[0];
}
测试：
echo highestPlus(range(0,11));//echoes 12
$arr = array(9,3,4,1,2,5);
echo highestPlus($arr);//echoes 6
现在，无耻地窃取 Pé de Leão 的答案(但"增强">它以完全按照您的要求(：
function highestPlus(array $range)
{//an unreadable one-liner... horrid, so don't, but know that you can...
return min(array_diff(range(0, max($range)+1), $range)) ?: max($range) +1;
}
工作原理：
$compare = range(min($in), max($in));//range(lowest value in array, highest value in array)
$diff = array_diff($compare, $in);//get all values present in $compare, that aren't in $in
return empty($diff) ? max($in) +1 : $diff[0];
//-------------------------------------------------
// read as:
if (empty($diff))
{//every number in min-max range was found in $in, return highest value +1
return max($in) + 1;
}
//there were numbers in min-max range, not present in $in, return first missing number:
return $diff[0];
这样，真的。
当然，如果提供的数组可能包含null或falsy值，甚至是字符串和重复值，那么"清理">输入可能会很有用：
function highestPlus(array $in)
{
$clean = array_filter(
$in,
'is_numeric'//or even is_int
);
$compare = range(min($clean), max($clean));
$diff = array_diff($compare, $clean);//duplicates aren't an issue here
return empty($diff) ? max($clean) + 1; $diff[0];
}
有用的链接：
array_diff手册页max和min功能- 好
range，当然... array_filter功能array_map函数可能值得一看- 就像
array_sum一样
$range = array(0,1,2,3,4,6,7);
// sort just in case the range is not in order
asort($range);
$range = array_values($range);
$indexes = array_keys($range);
$diff = array_diff($indexes,$range);
echo $diff[0]; // >> will print: 5
// if $diff is an empty array - you can print
// the "maximum value of the range plus one": $range[count($range)-1]+1
echo min(array_diff(range(0, max($range)+1), $range));
Simple
$array1 = array(0,1,2,3,4,5,6,7);// array with actual number series
$array2 = array(0,1,2,4,6,7); // array with your custom number series
$missing = array_diff($array1,$array2);
sort($missing);
echo $missing[0];
$range = array(0,1,2,3,4,6,7);
$max=max($range);
$expected_total=($max*($max+1))/2; // sum if no number was missing.
$actual_total=array_sum($range); // sum of the input array.
if($expected_total==$actual_total){
echo $max+1; // no difference so no missing number, then echo 1+ missing number.
}else{
echo $expected_total-$actual_total; // the difference will be the missing number.
}
像这样使用array_diff()
<?php
$range = array("0","1","2","3","4","6","7","9");
asort($range);
$len=count($range);
if($range[$len-1]==$len-1){
$r=$range[$len-1];
}
else{
$ref= range(0,$len-1);
$result = array_diff($ref,$range);
$r=implode($result);
}
echo $r;
?>
function missing( $v ) {
static $p = -1;
$d = $v - $p - 1;
$p = $v;
return $d?1:0;
}
$result = array_search( 1, array_map( "missing", $ARRAY_TO_TEST ) );