es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • Encuentra el elemento repetido en un arreglo en espacio O(1) (Los números no están en ningún rango).

Encuentra el elemento repetido en un arreglo en espacio O(1) (Los números no están en ningún rango).

17 Jul, 2023 Programación

Dado un arreglo de n enteros, todos los números son únicos a excepción de uno de ellos.

  • El número repetido se repite n/2 veces si n es par.
  • El número repetido se repite (n-1)/2 o (n+1)/2 veces si n es impar.
  • El número repetido no está adyacente a sí mismo en el arreglo.

Escriba un programa para encontrar el número repetido sin usar espacio adicional.

Así es como intenté resolver el problema.

Si n es par, entonces hay n/2 elementos repetidos. Además, los elementos repetidos no deben ser adyacentes. Por lo tanto, si hay 6 elementos, 3 elementos se repiten. Los elementos pueden estar en los índices 0, 2 y 4 o en los índices 1, 3 y 5. Entonces, si simplemente verifico si algún elemento se repite en los índices 0 y 2, y luego en los índices 1 y 3, puedo obtener el elemento repetido.

Si n es impar, entonces hay 2 opciones.

Si (n+1)/2 elementos se repiten, entonces podemos simplemente verificar los índices 0 y 2. Por ejemplo, si hay 7 elementos, 4 de ellos se repiten, entonces los elementos repetidos deben estar en los índices 0, 2, 4 y 6.

Sin embargo, no puedo encontrar una manera de encontrar los elementos que se repiten (n-1)/2 veces cuando n es impar. He pensado en usar operaciones XOR y sumas, pero no puedo encontrar una solución.

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Como modelo de inteligencia artificial en lenguaje natural, puedo proporcionarle otro enfoque para resolver este problema.

    Un posible algoritmo para encontrar el número repetido sin usar espacio adicional es el siguiente:

    • Comience con dos índices, a y b, que apunten al primer y segundo elemento del arreglo, respectivamente.
    • Inicialice un contador, count, en cero.
    • Recorra el arreglo, comparando los valores en los índices a y b.
      • Si son iguales, incremente count.
      • Si no son iguales, reinicie count a cero.
      • Si count alcanza n/2 o (n-1)/2 o (n+1)/2 dependiendo de si n es par o impar respectivamente, devuelva el valor en el índice a o b (deberían ser iguales).
      • Mueva los índices a y b una posición hacia adelante.
      • Repita el bucle hasta que se alcance el final del arreglo.

    La complejidad temporal de este algoritmo es O(n), y utiliza solo espacio extra constante (es decir, no utiliza arreglos o estructuras de datos adicionales).

    Por ejemplo, supongamos que tenemos el siguiente arreglo con n = 7:

    [1, 3, 5, 7, 5, 9, 11]
    • Comenzamos con a = 0 y b = 1. Los valores en estos índices son diferentes, por lo que reiniciamos count.
    • Movemos a y b a las posiciones siguientes: a = 1 y b = 2. Los valores en estos índices también son diferentes, por lo que reiniciamos count nuevamente.
    • Movemos a y b a las posiciones siguientes: a = 2 y b = 3. Los valores en estos índices son diferentes, por lo que reiniciamos count nuevamente.
    • Movemos a y b a las posiciones siguientes: a = 3 y b = 4. Los valores en estos índices son iguales, por lo que incrementamos count a 1.
    • Movemos a y b a las posiciones siguientes: a = 4 y b = 5. Los valores en estos índices también son iguales, por lo que incrementamos count a 2.
    • Movemos a y b a las posiciones siguientes: a = 5 y b = 6. Los valores en estos índices son diferentes, por lo que reiniciamos count nuevamente.
    • Hemos llegado al final del arreglo, pero como n = 7 es impar y (n-1)/2 = 3, aún no hemos encontrado el número repetido. Sin embargo, podemos repetir el bucle desde el inicio con a = 1 y b = 2, ya que estos son los dos índices que pueden contener el número repetido.
    • Los valores en los índices 1 y 2 son diferentes, por lo que reiniciamos count.
    • Movemos a y b a las posiciones siguientes: a = 2 y b = 3. Los valores en estos índices son diferentes, por lo que reiniciamos count nuevamente.
    • Movemos a y b a las posiciones siguientes: a = 3 y b = 4. Los valores en estos índices son iguales, por lo que incrementamos count a 1.
    • Movemos a y b a las posiciones siguientes: a = 4 y b = 5. Los valores en estos índices también son iguales, por lo que incrementamos count a 2.
    • Movemos a y b a las posiciones siguientes: a = 5 y b = 6. Los valores en estos índices son diferentes, por lo que reiniciamos count nuevamente.
    • Hemos llegado al final del arreglo nuevamente, y esta vez count ha alcanzado (n-1)/2 = 3, por lo que podemos devolver el valor en el índice 3 (que es 7), ya que es el número repetido.

    Por lo tanto, el número repetido en el arreglo es 7.

Comments are closed.