如何使用 PHP 查找序列中的缺失值?

2022-01-20 00:00:00 algorithm find php

假设您有一个数组值 => 时间戳".这些值随着时间的推移而增加,但可以随时重置.

Suppose you have an array "value => timestamp". The values are increasing with the time but they can be reset at any moment.

例如:

$array = array(
1 => 6000,
2 => 7000,
3 => 8000,
7 => 9000,
8 => 10000,
9 => 11000,
55 => 1000,
56 => 2000,
57 => 3000,
59 => 4000,
60 => 5000,
);

我想从这个数组中检索所有缺失的值.

I would like to retrieve all the missing values from this array.

这个例子会返回:

array(4,5,6,58)

我不想要 9 到 55 之间的所有值,因为 9 比其他更高的值更新.

I don't want all the values between 9 and 55 because 9 is newer than the other higher values.

在实际情况下,脚本将处理数千个值,因此它需要高效.

In real condition the script will deal with thousands of values so it need to be efficient.

感谢您的帮助!

更新:如果算法更容易,初始数组可以按时间戳排序.

UPDATE : The initial array can be ordered by timestamps if it is easier for the algorithm.

更新 2:在我的示例中,这些值是 UNIX 时间戳,因此它们看起来更像这样:1285242603 但出于可读性原因,我对其进行了简化.

UPDATE 2 : In my example the values are UNIX timestamps so they would look more like this : 1285242603 but for readability reason I simplified it.

推荐答案

这是另一个解决方案:

$prev = null;
$missing = array();
foreach ($array as $curr => $value) {
    if (!is_null($prev)) {
        if ($curr > $prev+1 && $value > $array[$prev]) {
            $missing = array_merge($missing, range($prev+1, $curr-1));
        }
    }
    $prev = $curr;
}

相关文章