可以在for循环从这块PHP code的淘汰？ [英] Can the for loop be eliminated from this piece of PHP code?

问题描述

我有一个范围，可能会或可能不会有一些数字丢失整个数字。是有可能找到最小丢失的数目，而无需使用一个环结构？如果没有缺号，函数应该返回范围内的最大值加1。

这是我如何解决它使用为循环：

  $范围= [0,1,2,3,4,6,7];//排序以防万一的范围是不是为了
ASORT（$范围）;
$范围= array_values​​（$范围）;$第一= TRUE;
为（$ X = 0; $ X＆LT;计数（$范围）; $ X ++）
{
    //不检查的第一要素
    如果（！$第一）
    {
        如果（$范围[$ X  -  1]！+ 1 == $范围[$ X]）
        {
            回声$范围[$ X  -  1] + 1;
            打破;
        }
    }    //如果我们的最后一个元素上，没有缺号
    如果（$ X + 1 ===计数（$范围））
    {
        回声$范围[$ X] + 1;
    }
    $第一= FALSE;
}
 

在理想情况下，我想完全避免循环，因为范围可以是巨大的。有什么建议？

解决方案

  

编辑：注意结果
  这个问题是关于性能。像功能和array_diff 和 array_filter 不是奇迹般地快。他们可以添加一个巨大时间损失。在code通过调用和array_diff 更换循环不会神奇地把事情快，和将可能使事情变得更慢。您需要了解这些功能是如何工作的，如果你打算使用它们来加快您的code。

  
  

这个回答使用了没有项目是重复的假设，没有无效的元素存在，使我们能够用它来推断其预期值的元素的位置。

  
  

这答案是理论上最快的解决方案如果你开始与排序列表即可。发表杰克解决方案是理论上如果排序所需的最快的。

在系列[0,1,2,3,4，...]，在 N 的'个元素的值的 N 的如果说之前没有元素缺失。因此，我们可以在任何时候抽查，看是否我们缺少的元素的前的或的之后的有问题的元素。

所以，你通过削减一半的名单和检查，看看是否开始在位置的项目X = X

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

啊，列表[4] == 4 。因此，从目前的中途移动列表的末尾。

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

嗯，哦，列表[6] == 7 。我们的最后一个检查点和当前的地方所以，一个元素失踪了。分差一半，并检查元素：

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

在这种情况下，列表[5] == 5

所以，我们是好那里。因此，我们采取我们目前的检查，最后一个，这是不正常之间距离的一半。哦..它看起来像细胞 N + 1 是一个我们已经检查。我们知道，列表[6] == 7 和列表[5] == 5 ，所以元素数6是缺少一个。

由于每个步骤分为两半来考虑的元素数量，你知道你的最坏情况下的性能将会比检查总表大小的日志 ₂ 没了。也就是说，这是一个 O（日志（N））解决方案。

如果这整个的安排看起来很熟悉，这是因为你在大学的第二年计算机科学课上学回来。它是在二进制搜索算法轻微变化的在最广泛使用的索引图的--one行业。事实上，这个问题似乎是为这个搜索技术的一个非常做作的应用程序。

您当然可以重复操作，以找到更多缺少的元素，但既然你已经在列表中的关键要素测试的值，可以避免重新检查最名单，直接进入到左有趣的来检验。

另外请注意，这种解决方案假定排序列表。如果列表中的不是的排序那么显然你先排序。除了二进制搜索有一些共同的显着性与快速排序。它很可能，你可以在一个单一的操作过程中结合了发现缺少元素的过程中分拣和两者都做，自己节省一些时间。

最后，总结一下名单，这只是扔在良好的措施一个愚蠢的数学把戏。从1到N数字列表的总和就是 N *（N + 1）/ 2 。如果您已经确定过任何元素缺失，则obvously只是减去缺少的。

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.

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?

解决方案

EDIT: 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.

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.

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.

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 ]
                  ^

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 ]
                          ^

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 ]
                      ^

In this case, list[5] == 5

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.

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.

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.

这篇关于可以在for循环从这块PHP code的淘汰？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！