Как найти пропущенные значения в последовательности с PHP?

Question

Предположим, у вас есть массив "value => timestamp". Значения увеличиваются со временем, но их можно сбросить в любой момент.

Например:

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

Я хотел бы получить все недостающие значения из этого массива.

Этот пример вернет:

array(4,5,6,58)

Мне не нужны все значения от 9 до 55, потому что 9 новее, чем другие более высокие значения.

В реальных условиях скрипт будет работать с тысячами значений, поэтому он должен быть эффективным.

Спасибо за вашу помощь!

---

ОБНОВЛЕНИЕ: Исходный массив можно упорядочить по временным меткам, если это проще для алгоритма.

---

ОБНОВЛЕНИЕ 2: В моем примере значения являются временными метками UNIX, поэтому они будут выглядеть примерно так: 1285242603, но по причине читабельности я упростил его.

Answer 1

Вот еще одно решение:

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

Answer 2

Это дает желаемый результат array(4,5,6,58):

$previous_value = NULL;
$temp_store = array();
$missing = array();
$keys = array_keys($array);

for($i = min($keys); $i <= max($keys); $i++)
{
    if(!array_key_exists($i, $array))
    {
        $temp_store[] = $i;
    }
    else
    {
        if($previous_value < $array[$i])
        {
            $missing = array_merge($missing, $temp_store);
        }
        $temp_store = array();
        $previous_value = $array[$i];
    }
}

var_dump($missing);

Или просто используйте очень умное решение Gumbo; -)

Answer 3

Вы можете сделать следующее:

• Продолжать сравнивать смежные ключи массива.Если они являются последовательными, вы ничего не делаете.
• Если они не являются последовательными, то вы проверяете их значения. Если значение упало с более высокого значения до более низкого, это означает, что произошел сброс, поэтому вы ничего не делаете.
• Если значение не упало, то это случай отсутствия ключа (ей).Все числа между двумя ключами (крайние значения не включены) являются частью результата.

Переведено в код:

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

$keys = array_keys($array);
for($i=0;$i<count($array)-1;$i++) {
  if($array[$keys[$i]] < $array[$keys[$i+1]] && ($keys[$i+1]-$keys[$i] != 1) ) {
           print(implode(' ',range($keys[$i]+1,$keys[$i+1]-1)));
           print "\n";
   }   
}

Рабочая ссылка