java - repiten - Encuentra solo un número que se repite en un millón de número(s)

numero repetido y cantidad de veces que se repite en java

Question

Este enigma me fue preguntado recientemente en una entrevista de adobe: - Hay una matriz que contiene millones de números positivos desordenados donde todos los elementos son distintos excepto por un número que ocurre exactamente dos veces. El motivo es encontrar ese número que ocurre dos veces de la manera más óptima.

PS Absolutamente no hay orden / patrón aplicable a la matriz.

El entrevistador rechazó la posibilidad de cualquier tipo, ya que tomaría mucho tiempo, quería que la pregunta se tomara como un acertijo y luego proponer una solución más inteligente.

Answer 1

Como los datos no están ordenados, debe verificar cada número contra el resto (n-1), por lo tanto, O (n ^ 2). Están pidiendo ese algoritmo que tiene una complejidad de tiempo inferior a O (n ^ 2). Para esto, necesitas una tabla de árbol o hash. Si clasificas esos datos y luego aplicas cualquier algoritmo, ese será un proceso que consumirá más tiempo. Para ambas tablas de árbol y hash, necesitarás O (n). Ya que son los mejores para organizar datos y encontrar datos.

Answer 2

El primer enfoque sería simplemente ordenar la matriz y luego pasar por los datos ordenados hasta que encuentre dos números idénticos consecutivos. Esto podría hacerse fácilmente en el tiempo O(n log n) y el espacio O(1) .

Si el entrevistador pregunta si hay una forma mejor, entonces analizará las limitaciones que puedan existir en los datos (el orden / patrón no implica necesariamente ninguna limitación en los datos). También debe preguntarse qué es lo que realmente significan por óptimo: el término en sí mismo significa poco sin medir una cantidad.

Algunas personas optimizan el tiempo, otras el espacio, otras (como yo) incluso optimizan la legibilidad del código :-)

En términos de discutir limitaciones, un ejemplo sería si el rango de los números estaba limitado a varios millones. Entonces sería una simple cuestión crear una matriz de conteos y procesar todos los datos en tiempo O(n) con algo como:

dim array[several million] as zero
for each number:
    array[number]++
    if array[number] == 2:
        print number
        stop

Incluso sin esa limitación, un rango numérico de 32 bits podría usar una matriz de cuatro mil millones de bits (aproximadamente 500M), y ese es su ejemplo clásico de espacio comercial por tiempo.

Tenga en cuenta que las preguntas de la entrevista no intentan descubrir si tiene una solución para un problema determinado, sino que el entrevistador puede ver sus procesos de pensamiento. Muy a menudo, su mayor activo no es un conocimiento enciclopédico de los algoritmos, es su capacidad para pensar de forma inteligente sobre los problemas y cómo resolverlos.

Answer 3

Un solo pase secuencial a través de la matriz con hash los valores en un conjunto me dirá el duplicado. Esto es O (n), pero usa estructuras de memoria y datos para el HashSet. El peor caso para Hashing se duplica en el primero y el último lugar.

Clasificar incluso hasta 25M de enteros es rápido, ~ 2 segundos, y - aunque O (n log n) - tiene un tiempo relativamente constante, y es mucho más rápido que el peor caso para el hash. OTOH, hashing puede superar la clasificación, así como el siguiente método:

Lo más rápido es usar un BitMap para registrar números (~ 1 seg), aunque esto puede requerir una cantidad considerable de memoria ((0x7FFF_FFFF + 1) / 8, es decir, el número de enteros no negativos divididos por bits por bytes), pero aquí la asignación es directa. Nuevamente, el peor de los casos es duplicado en el primer y último lugar.

Aquí está el código que he usado para comparar. Debería ser tomado con cuidado, como la mayoría de los puntos de referencia ingenuos en Java. Pero muestra que la legibilidad del código no es un problema con ninguno de los enfoques.

public class Duplicate {
    public static void main(String[] args) throws Exception {
        Random r = new Random( 100L );
        int[] a = new int[25000000];
        Set<Integer> set  = new HashSet<>(a.length/2);
        boolean dupl = true;
        for( int i = 0; i < a.length; ){
            int x = Math.abs( r.nextInt() );
            if( set.add( x ) ){
                a[i++] = x;
            }
        }
        a[a.length-1] = a[0]; // Worst case for HashSet and BitSet
        set = null;

        System.out.println( "hash " + new Date() );
        set  = new HashSet<>();
        for( int i = 0; i < a.length; ++i ){
            if( ! set.add( a[i] ) ){
                System.out.println( a[i] );
                break;
            }
        }
        set = null;

        System.out.println( "bitmap " + new Date() );
        BitSet bs = new BitSet( 0x7FFF_FFFF ); 
        for( int i = 0; i < a.length; ++i ){
            if( bs.get( a[i]-1 ) ){
                System.out.println( a[i] );
                break;
            }
            bs.set( a[i]-1 );
        }

        System.out.println( "sort "  + new Date());
        Arrays.sort( a );
        for( int i = 1; i < a.length; ++ i ){
            if( a[i] == a[i-1] ){
                System.out.println( a[i] );
                break;
            }
        }
        System.out.println( "done " + new Date() );
    }
}

Más tarde Tenga en cuenta que Java 8 tiene Arrays.sortParallel. Dado que tienes HW, esto reducirá aún más el tiempo de ordenamiento. - También tenga en cuenta que el método de establecimiento de bits se basa en las especificaciones "números positivos". Se complicaría la cuestión si se incluyeran números negativos, pero sospecho que los entrevistadores querían aprender sobre la "fluidez" del candidato con respecto a los recursos java.util de Java.