algorithm - prim - Cómo hacer que la complejidad del espacio sea O(1)

orden de complejidad dijkstra

Question

Estoy tratando de responder la siguiente pregunta: Usted tiene una matriz de enteros, de modo que cada entero está presente un número impar de tiempo, excepto 3 de ellos. Encuentra los tres números.

Hasta aquí vine con el método de la fuerza bruta:

 public static void main(String[] args) {
    // TODO Auto-generated method stub

    int number[] = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };
    FindEvenOccurance findEven = new FindEvenOccurance();
    findEven.getEvenDuplicates(number);

  }

  // Brute force
  private void getEvenDuplicates(int[] number) {

    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    for (int i : number) {

      if (map.containsKey(i)) {
        // a XOR a XOR a ---- - -- - - odd times = a
        // a XOR a ---- -- -- --- - even times = 0
        int value = map.get(i) ^ i;
        map.put(i,value);
      } else {
        map.put(i, i);
      }
    }

    for (Entry<Integer, Integer> entry : map.entrySet()) {

      if (entry.getValue() == 0) {
        System.out.println(entry.getKey());
      }

    }
  }

Funciona bien pero no es eficiente.

La o / p:

1
5
6
8

Pero las preguntas especifican que necesitamos hacer esto en el espacio O (1) y en la complejidad del tiempo O (N). Para mi solución, la complejidad del tiempo es O (N) pero espacio también O (N). ¿Puede alguien sugerirme una mejor manera de hacer esto con el espacio O (1)?

Gracias.

Answer 1

Desafortunadamente, no es posible lograr tal solución con espacio O (1) y complejidad O (n) si usamos un sentido estricto del espacio, es decir, el espacio O (1) está limitado por el espacio máximo utilizado en la matriz de entrada.

En un sentido débil de espacio, donde un número entero grande arbitrario todavía cabe en O (1), puede codificar su contador en los bits de este entero. Comience con todos los bits establecidos en 1. Alterne el n-ésimo bit cuando encuentre el número n en la matriz de entrada. Todos los bits que quedan 1 al final representan los 3 números que se encontraron un número par de veces.

Answer 2

Hay dos formas de ver tu problema.

La primera forma, como un problema matemático con un conjunto infinito de enteros, parece sin solución.

La segunda forma, como un problema de computación con un conjunto de enteros finitos, ya lo resolvió (¡felicitaciones!). Por qué ? Debido a que el espacio de almacenamiento está limitado por MAX_INT, independientemente de N.

NB: una optimización de espacio obvia sería almacenar los valores solo una vez, borrando el valor anterior para conteos pares, ganará la mitad del espacio.

Acerca de las otras respuestas de @Lashane y @ SGM1: también resuelven el problema de "computación", pero posiblemente sean menos eficientes que las suyas en la mayoría de los escenarios del mundo real. Por qué ? Debido a que asignan previamente una matriz de 512 MB, en lugar de asignar proporcionalmente al número de valores diferentes en la matriz. Como es probable que la matriz use valores mucho menores que MAX_INT diferentes, es probable que use valores mucho menores que 512 MB, incluso si almacena 32 bits para cada valor en lugar de 1. Y eso es con números enteros de 32 bits, con más bits que los anteriores. la matriz asignada crecería exponencialmente, OTOH su solución solo depende de los valores reales de la matriz, por lo que no se ve afectada por la cantidad de bits del sistema (es decir, el valor máximo int).

Vea también this y this para mejores algoritmos (menos espacio).

Answer 3

Mi intento por la respuesta, usando la propuesta de Lashane de una manera ligeramente diferente:

char negBits[268435456]; // 2 ^ 28 = 2 ^ 30 (number of negative integer numbers) / 8 (size of char) char posBits[268435456]; // ditto except positive int number[] = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 }; for (int num : number){ if (num < 0){ num = -(num + 1);// Integer.MIN_VALUE would be excluded without this + 1 negBits[ << 4] ^= ((num & 0xf) >> 1); } else { posBits[num << 4] ^= ((num & 0xf) >> 1); // grab the rite char to mess with // toggle the bit to represent the integer value. } } // Now the hard part, find what values after all the toggling: for (int i = 0; i < Integer.MAX_VALUE; i++){ if (negBits[i << 4] & ((i & 0xf) >> 1)){ System.out.print(" " + (-i - 1)); } if (posBits[i << 4] & ((i & 0xf) >> 1)){ System.out.print(" " + i); } }

De acuerdo con la discusión en los comentarios, los siguientes puntos son dignos de mención para esta respuesta:

• Asume Java en 32 bit.
• La matriz de Java tiene un límite inherente de Integer.MAX_INT

Answer 4

Pasé un tiempo resolviendo este problema. Parece que encontré solución. En cualquier caso, creo que esa comunidad me ayudará a verificar las ideas que se enumeran a continuación.

En primer lugar, afirmo que podemos resolver este problema cuando el número de enteros no emparejados es igual a 1 o 2 . En el caso de 1 entero no pareado, solo necesitamos encontrar XOR de todos los elementos de la matriz y será la respuesta. En el caso de 2 enteros no emparejados, la solución se vuelve más complicada. Pero ya fue discutido anteriormente. Por ejemplo puedes encontrarlo here .

Ahora intentemos resolver el problema cuando el número de enteros no emparejados es igual a 3 .

Al principio también calculamos XOR de todos los elementos. Vamos a denotar como X.

Considere el i-th bit en X. Supongo que es igual a 0 . Si es igual a 1, el siguiente procedimiento es prácticamente el mismo, simplemente cambiamos de 0 a 1 y viceversa.

Entonces, si el i-th en el bit X es igual a 0 tenemos dos situaciones posibles. Una situación es cuando todos los enteros no emparejados tienen 0 en el bit i-th . Otra situación es cuando un entero no pareado tiene 0 en el bit i-th , y dos enteros no pareados tienen 1 en el bit i-th . Esta declaración se basa en propiedades de operación XOR simple. Entonces tenemos uno o tres enteros no emparejados con 0 en el bit i-th .

Ahora dividamos todos los elementos en los dos grupos. El primer grupo es para enteros con 0 en la posición del bit i-th , el segundo es para números enteros con 1 en la posición del bit i-th . También nuestro primer grupo contiene uno o tres enteros no emparejados con ''0'' en el bit i-th .

¿Cómo podemos obtener cierto número de enteros no emparejados en el primer grupo? Solo necesitamos calcular XOR de todos los elementos en el segundo grupo. Si es igual a cero, entonces todos los enteros no emparejados están en el primer grupo y debemos verificar otro i . En el otro caso, solo hay un entero no pareado en el primer grupo y otros dos en el segundo, y podemos resolver el problema por separado para estos dos grupos usando métodos desde el principio de esta respuesta.

La observación clave es que hay i tal que un entero no pareado tiene un bit i-th que difiere de los bits i-th de los otros dos enteros no pareados. En este caso, los enteros no emparejados están en ambos grupos. Se basa en el hecho de que si no hay tal i, entonces los bits en todas las posiciones en enteros no emparejados son similares y son iguales entre sí. Pero es imposible de acuerdo con la declaración del problema.

Esta solución se puede implementar sin ninguna memoria adicional. La complejidad total es lineal con algunas constantes dependiendo del número de bits en los elementos de la matriz.

Answer 5

Su esquema del problema y el ejemplo no coinciden. Dice que está buscando 3 enteros en su pregunta, pero el ejemplo muestra 4.

No estoy seguro de que esto sea posible sin restricciones adicionales. Me parece que la complejidad del tamaño del caso más desfavorable siempre será al menos O (N-6) => O (N) sin una lista ordenada y con el conjunto completo de enteros.

Si comenzamos con una matriz ordenada, entonces sí, fácil, pero esta restricción no está especificada. Ordenar el arreglo nosotros mismos será demasiado complejo de tiempo o espacio.

Answer 6

considere, por ejemplo, que los números permitidos son de tamaño 4 bits , lo que significa el rango de números permitido de 0 a 2 ⁴ -1, que es un número constante 16 , por cada entrada posible que ejecutamos en toda la matriz y xo la aparición de este número, si el resultado de xor es cero, agregamos valor actual al resultado general. esta solución es O (16N) que es O (N) y usa solo una variable adicional para evaluar el xor del número actual que es O (1) en términos de complejidad de espacio.

podemos extender este método a nuestro problema original, pero tendrá un número constante muy grande en términos de complejidad de tiempo de ejecución que será proporcional al número de bits permitido en la entrada original.

podemos mejorar este enfoque ejecutando todos los elementos y encontrar el bit más significativo sobre todos los datos de entrada, supongamos que es el ^décimo bit, entonces nuestra complejidad en el tiempo de ejecución se convertirá en O (2 ¹⁰ N), que también es O (N) .

Otra mejora se puede encontrar en la imagen de abajo, pero aún con la peor complejidad del caso como se explicó anteriormente.

Finalmente creo que existe otra solución mejor para este problema, pero decidí compartir mi pensamiento.

Editar:

El algoritmo en la imagen puede no estar claro, aquí hay una explicación del algoritmo.
comienza con la idea de tratar de dividir los elementos según los bits, en otras palabras, haga los bits como un filtro, en cada etapa xo los elementos divididos, hasta que el resultado xor sea cero, entonces vale la pena marcar este grupo uno por uno, ya que seguramente contendrá al menos una de las salidas deseadas. o si dos filtros consultivos resultan en el mismo tamaño, detendremos este filtro, será más claro con el siguiente ejemplo.
entrada: 1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9
Comenzamos dividiendo los elementos de acuerdo con el bit Menos significativo.
Primer bit cero : 6,4,4,8,8,4,6,8,8
6 xor 4 xor 4 xor 8 xor 8 xor 4 xor 6 xor 8 xor 8 = 4
por lo que continuaremos dividiendo este grupo de acuerdo con el segundo bit.
1 ^st bit zero y 2 ^nd bit zero : 4,4,4,8,8,8,8
4 xor 4 xor 4 xor 8 xor 8 xor 8 xor 8 xor 8 = 4.
por lo que continuaremos dividiendo este grupo de acuerdo con el 3er bit.
1 ^st bit zero y 2 ^nd bit zero y 3 ^rd bit zero : 8,8,8,8
8 xor 8 xor 8 xor 8 = 0
así que veremos cada elemento debajo de este filtro porque el resultado de xor es cero y agregaremos 8 a nuestro resultado hasta ahora.
1 ^st bit zero y 2 ^nd bit zero y 3 ^rd bit one : 4,4,4
4 xor 4 xor 4 = 4
1 ^st bit zero y 2 ^nd bit zero y 3 ^rd bit one y 4 ^th bit zero : 4,4,4
4 xor 4 xor 4 = 4.
así que nos detendremos aquí ya que este filtro contiene el mismo tamaño que el filtro anterior
Ahora volveremos al filtro de ^1ª y ^2ª bit.
1 ^st bit zero y 2 ^nd bit one : 6,6
6 xor 6 = 0.
así que veremos cada elemento debajo de este filtro porque el resultado de xor es cero y agregaremos 6 a nuestro resultado hasta ahora.
Ahora volveremos al filtro de 1 ^st bit.
Primer bit uno : 9,5,9,7,9,1,1
Ahora continuaremos bajo este filtro como el mismo procedimiento anterior.
para el ejemplo completo vea la imagen de arriba.