php - 这段PHP代码可以去掉for循环吗？

Question

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

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

算法解决方案

有一种方法可以使用算法检查是否有缺失的数字。解释了here .基本上，如果我们需要将 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

Online demo

如果缺少几个数字，则只需使用 array_map() 或类似的东西来进行内部循环。

---

正则表达式解决方案

让我们将其提升到一个新的水平并使用正则表达式!我知道这是无稽之谈，不应该在实际应用中使用。目标是展示正则表达式的真正力量 :)

所以首先让我们按照以下格式在我们的范围之外创建一个字符串:I,II,III,IIII for 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;

output应该是这样的:I,II,III,IIII,IIII,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.

See it working and failing .让我们把它放在 PHP code 中:

$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
}

Online demo