PHP: Le nombre d'éléments consécutifs dans le tableau

J'ai travaillé sur un problème:

Trouvez le groupe le plus important de numéros consécutifs dans la matrice.

Disons que nous avons un tableau
[5, 43, 4, 56, 3, 2, 44, 57, 58, 1]

, Le plus grand groupe de nombres consécutifs dans ce tableau 5 /1, 2, 3, 4, et 5/.

L'algorithme de solution doit être une complexité temporaire. O /n/.

J'ai résolu ce problème avec le code suivant ruby, Mais j'ai eu des problèmes de poster sur PHP, Comme demandé.


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
Invité:

Clement

Confirmation de:

N'est pas O /n/, Mais vous pouvez l'essayer:


// 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/;


Vous pouvez obtenir la longueur maximale de
max/$count/

.

Cette solution vous donne le tableau suivant:


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

Giselle

Confirmation de:

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

Constantine

Confirmation de:

Ici python /ma PHP Pas trop bon/, qui fait ce qui demande votre description dans o /n/, Si votre séquence diminue:


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


L'idée est que
lists

Prend en charge les ensembles Dick indexés par

Tout

Liste des éléments. Chaque fois que vous rencontrez un nouvel élément, le précédent et les ensembles suivants sont combinés s'ils sont présents.

Opération
update

Techniquement est
o/n/

, mais il n'est pas exacerbé par un cycle externe, car il ne peut y avoir que d'insertion
n

En kits par fusion. En général, que
o/n/


Si la séquence n'est pas triée, alors la confluence des ensembles +1 et -1 donne des difficultés not-so-good.

Pour répondre aux questions, connectez-vous ou registre