Я работаю над одной проблемой:
Найдите самую большую группу последовательных чисел в массиве.
Скажем, у нас есть массив [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
$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);
Это не O (n), но вы можете попробовать это:
// 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)
Вот питон (мой 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 дает не очень хорошую сложность.