PHP: количество последовательных элементов в массиве

Question

Я работал над одной проблемой:

Найти самую большую группу последовательных чисел в массиве.

Скажем, у нас есть массив [5, 43, 4, 56, 3, 2, 44, 57, 58, 1], самая большая группа последовательных чисел в этом массиве - 5 (1, 2, 3, 4 и 5).

Алгоритм решения должен быть временной сложностью O (n).

Я решил это со следующим кодом ruby, но мне трудно переносить его на PHP по мере необходимости.

arr = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4] 
result = [] 
stage = [] 
for i in arr: 
    if len(stage) > 0 and i != stage[-1]+1: 
     if len(stage) > 1: 
      result.append(stage) 
     stage = [] 
    stage.append(i) 
print result 

Answer 1

$a = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4]; 

$res = []; 
$stage = []; 

foreach($a as $i) { 
    if(count($stage) > 0 && $i != $stage[count($stage)-1]+1) { 
     if(count($stage) > 1) { 
      $res[] = $stage; 
     } 
     $stage = []; 
    } 
    $stage[] = $i; 

} 
print_r($res); 

Answer 2

Вот питон (мой PHP не слишком хорошо), что делает то, что просит ваше описание в O (N), если ваша последовательность убывает:

lists = dict() 
for i in val: 
    if i in lists: 
     continue 
    a = {i} 
    if (i + 1) in lists: 
     b = lists[i+1] 
     b.update(a) 
     a = b 
    if (i - 1) in lists: 
     b = lists[i-1] 
     # this messes up the complexity 
     for k in b: 
      lists[k] = a 
     a.update(b) 
    lists[i] = a 

Идея заключается в том что lists поддерживает набор индексов на все элементы в списке. Всякий раз, когда вы сталкиваетесь с новым элементом, предыдущий и следующий наборы объединяются, если они присутствуют.

update операция является технически o(n), но это не усугубляется внешним контуром, так как может быть только n вставки в наборы путем слияния. В целом o(n)

Если последовательность не сортируется, слияние наборов +1 и -1 дает не очень хорошую сложность.

Answer 3

Это не O (п), но вы можете попробовать это:

// Define array 
$array = array(5,8,3,2,10,11,15,13,12,1,4,5,16); 

// Sorting 
asort($array); 

$previous = null; 
$result = array(); 
$consecutiveArray = array(); 

// Slice array by consecutive sequences 
foreach($array as $number) { 
    if ($number == $previous + 1) { 
     $consecutiveArray[] = $number; 
    } else { 
     $result[] = $consecutiveArray; 
     $consecutiveArray = array($number); 
    } 
    $previous = $number; 
} 
$result[] = $consecutiveArray; 

// Get length of each sub array 
$count = array_map('count', $result); 

Вы можете получить максимальную длину от max($count).

Это решение дает следующий массив:

array(
    0 => array(1,2,3,4,5) 
    1 => array(5) 
    2 => array(8) 
    3 => array(10,11,12,13) 
    4 => array(15,16)