La plus longue séquence de nombres

Question

On m'a récemment posé cette question dans une interview pour laquelle je pouvais donner une solution O (nlogn), mais je n'ai pas trouvé de logique pour O (n). Quelqu'un peut-il m'aider avec O (n) solution?

Dans un réseau trouver la longueur de la plus longue séquence de nombres

Exemple: entrée: 2 4 6 7 3 1 sortie: 4 (car 1,2,3,4 est une séquence, même si elles sont pas dans des positions consécutives)

La solution devrait également être réaliste en termes d'espace consommé. i.e la solution devrait être réaliste même avec un tableau de 1 milliard de chiffres

Answer 1

Pour les nombres non consécutifs, vous avez besoin d'un moyen de les trier en O(n). Dans ce cas, vous pouvez utiliser BitSet.

int[] ints = {2, 4, 6, 7, 3, 1}; 
BitSet bs = new BitSet(); 
IntStream.of(ints).forEach(bs::set); 

// you can search for the longer consecutive sequence. 
int last = 0, max = 0; 
do { 
    int set = bs.nextSetBit(last); 
    int clear = bs.nextClearBit(set + 1); 
    int len = clear - set; 
    if (len > max) 
     max = len; 
    last = clear; 
} while (last > 0); 
System.out.println(max); 

Answer 2

Traverse la matrice une fois et de construire la carte de hachage dont la clé est un numéro à partir du tableau d'entrée et de la valeur est une variable booléenne qui indique si l'élément a été traité ou non (initialement tous sont faux). Traversez une fois de plus et procédez comme suit: lorsque vous vérifiez le numéro a, mettez la valeur true pour cet élément dans la table de hachage et vérifiez immédiatement la table de hachage pour l'existence des éléments a-1 et a+1. Si cela est trouvé, notez leurs valeurs dans la table de hachage comme vrai et continuez à vérifier leurs voisins, en incrémentant la longueur de la sous-séquence contigue actuelle. Arrêtez s'il n'y a pas de voisins et mettez à jour la plus longue. Avancer dans le tableau et continuer à vérifier les éléments non traités. Il n'est pas évident au premier coup d'œil que cette solution soit O(n), mais il n'y a que deux traversées de tableaux et une table de hachage garantit que chaque élément de l'entrée n'est traité qu'une seule fois. Leçon principale - si vous devez réduire la complexité du temps, il est souvent nécessaire d'utiliser de l'espace supplémentaire.