这段PHP代码可以去掉for循环吗? [英] Can the for loop be eliminated from this piece of PHP code?

问题描述

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

I have a range of whole numbers that might or might not have some numbers missing. Is it possible to find the smallest missing number without using a loop structure? If there are no missing numbers, the function should return the maximum value of the range plus one.

这就是我使用 for 循环解决它的方法:

This is how I solved it using a for loop:

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

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

Ideally, I'd like to avoid looping completely, as the range can be massive. Any suggestions?

推荐答案

注意
这个问题是关于性能的.像 array_diff 和 array_filter 这样的函数并没有神奇的快.他们可以增加巨大的时间损失.使用对 array_diff 的调用替换代码中的循环不会神奇地使事情变快，并且可能会使事情变慢.如果您打算使用它们来加速您的代码，您需要了解这些函数是如何工作的.

NOTE
This question is about performance. Functions like array_diff and array_filter are not magically fast. They can add a huge time penalty. Replacing a loop in your code with a call to array_diff will not magically make things fast, and will probably make things slower. You need to understand how these functions work if you intend to use them to speed up your code.

这个答案假设没有重复的项目并且不存在无效元素，以允许我们使用元素的位置来推断其预期值.

This answer uses the assumption that no items are duplicated and no invalid elements exist to allow us to use the position of the element to infer its expected value.

这个答案理论上是最快的解决方案如果您从一个排序列表开始.如果需要排序，Jack 发布的解决方案理论上是最快的.

This answer is theoretically the fastest possible solution if you start with a sorted list. The solution posted by Jack is theoretically the fastest if sorting is required.

在系列 [0,1,2,3,4,...] 中，如果第 n 个元素之前没有元素，则其值为 n缺失.所以我们可以随时抽查，看看我们丢失的元素是before还是after有问题的元素.

In the series [0,1,2,3,4,...], the n'th element has the value n if no elements before it are missing. So we can spot-check at any point to see if our missing element is before or after the element in question.

因此，您首先将列表切成两半并检查位置 x = x 处的项目是否

So you start by cutting the list in half and checking to see if the item at position x = x

[ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ]
                  ^

是的，list[4] == 4.因此，从当前点移动到列表末尾.

Yup, list[4] == 4. So move halfway from your current point the end of the list.

[ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ]
                          ^

呃-哦，list[6] == 7.所以在我们最后一个检查点和当前检查点之间的某个地方，缺少一个元素.将差异一分为二并检查该元素:

Uh-oh, list[6] == 7. So somewhere between our last checkpoint and the current one, one element was missing. Divide the difference in half and check that element:

[ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ]
                      ^

在这种情况下，list[5] == 5

所以我们在那里很好.因此，我们将当前检查与上一次异常检查之间的距离减半.哦.. 看起来单元格 n+1 是我们已经检查过的单元格.我们知道 list[6]==7 和 list[5]==5，所以元素编号 6 是缺失的那个.

So we're good there. So we take half the distance between our current check and the last one that was abnormal. And oh.. it looks like cell n+1 is one we already checked. We know that list[6]==7 and list[5]==5, so the element number 6 is the one that's missing.

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

Since each step divides the number of elements to consider in half, you know that your worst-case performance is going to check no more than log₂ of the total list size. That is, this is an O(log(n)) solution.

如果整个安排看起来很熟悉，那是因为你在大学二年级的计算机科学课上学到了它.它是 二元搜索算法的一个小变体——它是当今最广泛使用的索引方案之一.行业.事实上，这个问题似乎是对这种搜索技术的完美设计.

If this whole arrangement looks familiar, It's because you learned it back in your second year of college in a Computer Science class. It's a minor variation on the binary search algorithm--one of the most widely used index schemes in the industry. Indeed this question appears to be a perfectly-contrived application for this searching technique.

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

You can of course repeat the operation to find additional missing elements, but since you've already tested the values at key elements in the list, you can avoid re-checking most of the list and go straight to the interesting ones left to test.

另请注意，此解决方案假定一个排序列表.如果列表未排序，那么显然您先对其进行排序.除此之外，二分查找与快速排序有一些显着的共同点.您很有可能将排序过程与查找缺失元素的过程结合起来，并在一个操作中同时完成，从而节省一些时间.

Also note that this solution assumes a sorted list. If the list isn't sorted then obviously you sort it first. Except, binary searching has some notable properties in common with quicksort. It's quite possible that you can combine the process of sorting with the process of finding the missing element and do both in a single operation, saving yourself some time.

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

Finally, to sum up the list, that's just a stupid math trick thrown in for good measure. The sum of a list of numbers from 1 to N is just N*(N+1)/2. And if you've already determined that any elements are missing, then obvously just subtract the missing ones.

这篇关于这段PHP代码可以去掉for循环吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！