可以从这段PHP代码中删除for循环吗？

Question

我有一系列可能会或可能不会丢失一些数字的整数.是否可以在不使用循环结构的情况下找到最小的缺失数字？如果没有缺失的数字,该函数应返回范围的最大值加1.

这就是我用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;
}

理想情况下,我想避免完全循环,因为范围可能很大.有什么建议？

Answer 1

Algo解决方案

有一种方法可以使用算法检查是否存在缺失的数字.它在这里解释.基本上,如果我们需要添加从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,IIIIfor range 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
}

在线演示

Answer 2

编辑:注意
这个问题是关于性能.功能喜欢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是缺少一个.

由于每个步骤将要考虑的元素数量分成两半,因此您知道最坏情况下的性能将检查不超过总列表大小的log ₂.也就是说,这是一个O(log(n))解决方案.

如果整个安排看起来很熟悉,那是因为你在大学二年级的计算机科学课上学到了这一点.它是二元搜索算法的一个小变化 - 是业界使用最广泛的指数方案之一.事实上,这个问题似乎是这种搜索技术的完美设计应用.

您当然可以重复该操作以查找其他缺失元素,但由于您已经测试了列表中关键元素的值,因此可以避免重新检查列表的大部分内容并直接转到剩下要测试的有趣元素.

另请注意,此解决方案假定排序列表.如果列表没有排序,那么显然你先排序.除此之外,二进制搜索与quicksort有一些共同的特性.很有可能你可以将排序过程与找到缺失元素的过程结合起来,并在一次操作中完成这两个过程,从而节省了一些时间.

最后,总结一下这个列表,这只是一个愚蠢的数学技巧.从1到N的数字列表的总和就是N*(N+1)/2.如果你已经确定缺少任何元素,那么只需减去遗漏的元素.

Answer 3

从技术上讲,你不能没有循环(除非你只想知道是否缺少数字).但是,您无需先对数组进行排序即可完成此操作.

以下算法使用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"条目是缺少的最小值.

顺便说一句,我使用临时字符串而不是数组来减少物理内存需求.

Answer 4

老实说,我不明白为什么你不想使用循环.循环没有问题.它们很快,你根本离不开它们.但是,在您的情况下,有一种方法可以避免使用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édeLeã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功能
• 好Ol' range,当然......
• 该array_filter功能
• 该array_map功能可能值得一看
• 就像array_sum可能一样