LeetCode – Secuencia consecutiva más larga (Java)

Dada una matriz de números enteros sin clasificar, calcule la longitud de la secuencia de elementos consecutivos más larga.

Por ejemplo, dado [100, 4, 200, 1, 3, 2], la secuencia de elementos consecutivos más larga debe ser [1, 2, 3, 4]. Su longitud es 4.

Su algoritmo debe ejecutarse en complejidad O (n).

Solución Java 1

Debido a que requiere complejidad O (n), no podemos resolver el problema ordenando la matriz primero. La clasificación lleva al menos O (nlogn) tiempo.

Podemos usar un HashSet para agregar y eliminar elementos. La agregar, retirar y contiene Los métodos tienen una complejidad de tiempo constante O (1).

public int longestConsecutive(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for(int num: nums) set.add(num);
 
    int result = 0;
 
    for(int num: nums){
        int count = 1;
 
        int down = num-1;
        while(set.contains(down)){
            set.remove(down);
            down--;
            count++;
        }
 
        int up = num+1;
        while(set.contains(up)){
            set.remove(up);
            up++;
            count++;
        }
 
        result = Math.max(result, count);
    }
 
    return result;
}

Solución Java 2

También podemos proyectar las matrices en una nueva matriz con la longitud para que sea el elemento más grande de la matriz. Luego, itera sobre la matriz y obtén la secuencia consecutiva más larga. Si el número más grande es muy grande, entonces la complejidad del tiempo sería mala.