arrays - para - obtener elementos repetidos en un array

¿Cómo encontrar un elemento duplicado en una matriz de enteros consecutivos mezclados?

Question

Recientemente encontré una pregunta en alguna parte:

Supongamos que tiene una matriz de 1001 enteros. Los enteros están en orden aleatorio, pero usted sabe que cada uno de los enteros está entre 1 y 1000 (inclusive). Además, cada número aparece solo una vez en la matriz, a excepción de un número, que aparece dos veces. Supongamos que puede acceder a cada elemento de la matriz solo una vez. Describe un algoritmo para encontrar el número repetido. Si usó almacenamiento auxiliar en su algoritmo, ¿puede encontrar un algoritmo que no lo requiera?

Lo que me interesa saber es la segunda parte , es decir, sin usar almacenamiento auxiliar . ¿Tiene alguna idea?

Answer 1

Una solución de línea en Python

arr = [1,3,2,4,2]
print reduce(lambda acc, (i, x): acc ^ i ^ x, enumerate(arr), 0)
# -> 2

La explicación sobre por qué funciona está en la respuesta de @Matthieu M.

Answer 2

¿Los argumentos y callstacks cuentan como almacenamiento auxiliar?

int sumRemaining(int* remaining, int count) {
    if (!count) {
        return 0;
    }
    return remaining[0] + sumRemaining(remaining + 1, count - 1);
}

printf("duplicate is %d", sumRemaining(array, 1001) - 500500);

Editar: versión de llamada final

int sumRemaining(int* remaining, int count, int sumSoFar) {
    if (!count) {
        return sumSoFar;
    }
    return sumRemaining(remaining + 1, count - 1, sumSoFar + remaining[0]);
}
printf("duplicate is %d", sumRemaining(array, 1001, 0) - 500500);

Answer 3

Agrega todos los números juntos. La suma final será el número duplicado de 1 + 2 + ... + 1000 +.

Answer 4

Agrega todos los números. La suma de los enteros 1..1000 es (1000 * 1001) / 2. La diferencia con lo que obtienes es tu número.

Answer 5

Apoyo la adición de todos los elementos y luego restarle la suma de todos los índices, pero esto no funcionará si la cantidad de elementos es muy grande. Es decir, ¡causará un desbordamiento de enteros! Así que he ideado este algoritmo que puede reducir las posibilidades de un desbordamiento de enteros en gran medida.

   for i=0 to n-1
        begin:  
              diff = a[i]-i;
              dup = dup + diff;
        end
   // where dup is the duplicate element..

¡Pero con este método no podré encontrar el índice en el que está presente el elemento duplicado!

Para eso necesito atravesar la matriz en otro momento que no es deseable.

Answer 6

Bueno, hay una manera muy simple de hacer esto ... cada uno de los números entre 1 y 1000 ocurre exactamente una vez, excepto el número que se repite ... entonces, la suma de 1 ... 1000 es 500500. Entonces, el algoritmo es:

sum = 0 for each element of the array: sum += that element of the array number_that_occurred_twice = sum - 500500

Answer 7

Mejora de la respuesta de Fraci basada en la propiedad de XORing valores consecutivos:

int result = xor_sum(N);
for (i = 0; i < N+1; i++)
{
   result = result ^ array[i];
}

Dónde:

// Compute (((1 xor 2) xor 3) .. xor value)
int xor_sum(int value)
{
    int modulo = x % 4;
    if (modulo == 0)
        return value;
    else if (modulo == 1)
        return 1;
    else if (modulo == 2)
        return i + 1;
    else
        return 0;
}

O en pseudocódigo / math lang f (n) definido como (optimizado):

if n mod 4 = 0 then X = n
if n mod 4 = 1 then X = 1
if n mod 4 = 2 then X = n+1
if n mod 4 = 3 then X = 0

Y en forma canónica f (n) es:

f(0) = 0
f(n) = f(n-1) xor n

Answer 8

Mi respuesta a la pregunta 2:

Encuentre la suma y el producto de los números de 1 - (a) N, diga SUM , PROD .

Encuentre la suma y el producto de Números de 1 - N- x -y, (suponga que falta x, y), diga mySum, myProd,

Así:

SUM = mySum + x + y;
PROD = myProd* x*y;

Así:

x*y = PROD/myProd; x+y = SUM - mySum;

Podemos encontrar x, y si resuelves esta ecuación.

Answer 9

Parafraseando la solución de Francis Penov.

El problema (habitual) es: dado un conjunto de enteros de longitud arbitraria que contienen solo elementos repetidos un par de veces pares excepto por un valor que se repite en tiempos impares, hallar este valor.

La solucion es:

acc = 0
for i in array: acc = acc ^ i

Tu problema actual es una adaptación. El truco consiste en encontrar el elemento que se repite dos veces, por lo que debe adaptar la solución para compensar esta peculiaridad.

acc = 0
for i in len(array): acc = acc ^ i ^ array[i]

Que es lo que hace la solución de Francis al final, aunque destruye toda la matriz (por cierto, solo podría destruir el primer o el último elemento ...)

Pero como necesita almacenamiento adicional para el índice, creo que se le perdonará si también usa un número entero adicional ... La restricción probablemente sea porque quieren evitar que use una matriz.

Habría sido redactado con mayor precisión si hubieran requerido O(1) espacio (1000 se puede ver como N ya que aquí es arbitrario).

Answer 10

Si sabe que tenemos los números exactos 1-1000, puede sumar los resultados y restar 500500 ( sum(1, 1000) ) del total. Esto dará el número repetido porque sum(array) = sum(1, 1000) + repeated number .

Answer 11

Sin requisitos de almacenamiento adicionales (aparte de la variable de bucle).

int length = (sizeof array) / (sizeof array[0]);
for(int i = 1; i < length; i++) {
   array[0] += array[i];
}

printf(
    "Answer : %d/n",
    ( array[0] - (length * (length + 1)) / 2 )
);

Answer 12

Solo agréguelos a todos y reste el total que esperaría si solo se usaran 1001 números.

P.ej:

Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10

Input - Expected => 2

Answer 13

Un triángulo número T (n) es la suma de los n números naturales de 1 a n. Se puede representar como n (n + 1) / 2. Por lo tanto, sabiendo que entre 1001 números naturales dados, uno y solo un número se duplica, puede sumar fácilmente todos los números dados y restar T (1000). El resultado contendrá este duplicado.

Para un número triangular T (n), si n es cualquier potencia de 10, también hay un hermoso método para encontrar esta T (n), basado en la representación de la base 10:

n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s

Answer 14

Una versión no destructiva de la solución de Franci Penov.

Esto puede hacerse haciendo uso del operador XOR .

Digamos que tenemos una matriz de tamaño 5 : 4, 3, 1, 2, 2
Que están en el índice: 0, 1, 2, 3, 4

Ahora haz un XOR de todos los elementos y todos los índices. Obtenemos 2 , que es el elemento duplicado. Esto sucede porque, 0 no juega ningún rol en el XORing. Los índices n-1 restantes se emparejan con los mismos elementos n-1 en la matriz y el único elemento no emparejado en la matriz será el duplicado.

int i;
int dupe = 0;
for(i = 0; i < N; i++) {
    dupe = dupe ^ arr[i] ^ i;
}
// dupe has the duplicate.

La mejor característica de esta solución es que no sufre problemas de desbordamiento que se ven en la solución basada en la adición.

Dado que esta es una pregunta de la entrevista, lo mejor sería comenzar con la solución de adición, identificar la limitación de desbordamiento y luego dar la solución basada en XOR :)

Esto hace uso de una variable adicional, por lo que no cumple completamente con los requisitos de la pregunta.

Answer 15

Actualización 2: Algunas personas piensan que usar XOR para encontrar el número duplicado es un truco o truco. A lo que mi respuesta oficial es: "No estoy buscando un número duplicado, estoy buscando un patrón duplicado en una matriz de conjuntos de bits. Y XOR definitivamente es mejor que ADD para manipular conjuntos de bits". :-)

Actualización: solo por diversión antes de acostarme, aquí hay una solución alternativa de "una línea" que no requiere almacenamiento adicional (ni siquiera un contador de bucle), toca cada elemento de matriz solo una vez, no es destructivo y no se escala en absoluto: -)

printf("Answer : %d/n",
           array[0] ^
           array[1] ^
           array[2] ^
           // continue typing...
           array[999] ^
           array[1000] ^
           1 ^
           2 ^
           // continue typing...
           999^
           1000
      );

Tenga en cuenta que el compilador realmente calculará la segunda mitad de esa expresión en tiempo de compilación, por lo que el "algoritmo" se ejecutará exactamente en 1002 operaciones.

Y si los valores del elemento de matriz también se conocen en tiempo de compilación, el compilador optimizará toda la instrucción a una constante. :-)

Solución original: que no cumple con los estrictos requisitos de las preguntas, aunque funciona para encontrar la respuesta correcta. Utiliza un entero adicional para mantener el contador de bucles, y accede a cada elemento de la matriz tres veces, dos veces para leerlo y escribirlo en la iteración actual y una vez para leerlo en la siguiente iteración.

Bueno, necesita al menos una variable adicional (o un registro de CPU) para almacenar el índice del elemento actual a medida que avanza en la matriz.

Sin embargo, aparte de ese, aquí hay un algoritmo destructivo que puede escalar con seguridad para cualquier N hasta MAX_INT.

for (int i = 1; i < 1001; i++)
{
   array[i] = array[i] ^ array[i-1] ^ i;
}

printf("Answer : %d/n", array[1000]);

Dejaré el ejercicio de averiguar por qué esto funciona para ti, con una simple pista :-):

a ^ a = 0
0 ^ a = a

Answer 16

public int duplicateNumber(int[] A) {
    int count = 0;
    for(int k = 0; k < A.Length; k++)
        count += A[k];
    return count - (A.Length * (A.Length - 1) >> 1);
}

Answer 17

public static void main(String[] args) {
    int start = 1;
    int end = 10;
    int arr[] = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10};
    System.out.println(findDuplicate(arr, start, end));
}

static int findDuplicate(int arr[], int start, int end) {

    int sumAll = 0;
    for(int i = start; i <= end; i++) {
        sumAll += i;
    }
    System.out.println(sumAll);
    int sumArrElem = 0;
    for(int e : arr) {
        sumArrElem += e;
    }
    System.out.println(sumArrElem);
    return sumArrElem - sumAll;
}

Answer 18

n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s