Algoritmo para buscar duplicados en una matriz

Question

Tengo una asignación para crear un algoritmo para buscar duplicados en una matriz que incluye valores numéricos. pero no ha dicho qué tipo de números, números enteros o flotantes. He escrito el siguiente pseudocódigo:

FindingDuplicateAlgorithm(A) // A is the array 
     mergeSort(A); 
     for int i <- 0 to i<A.length 
      if A[i] == A[i+1] 
       i++ 
       return A[i] 
      else 
       i++ 

¿he creado un algoritmo eficiente? Creo que hay un problema en mi algoritmo, devuelve números duplicados varias veces. por ejemplo, si array incluye 2 en dos para dos índices tendré ... 2, 2, ... en la salida. ¿Cómo puedo cambiarlo para devolver cada duplicado solo una vez? Creo que es un buen algoritmo para enteros, pero ¿funciona también para números flotantes?

Answer 1

Para manejar duplicados, puede hacer lo siguiente:

if A[i] == A[i+1]: 
    result.append(A[i]) # collect found duplicates in a list 
    while A[i] == A[i+1]: # skip the entire range of duplicates 
     i++    # until a new value is found 

Answer 2

No estoy seguro de en qué idioma necesita escribir el algoritmo, pero hay algunas soluciones de C++ realmente buenas en respuesta a my question aquí. Debería ser útil para usted.

Answer 3

Su algoritmo contiene un desbordamiento de búfer. i comienza con 0, por lo que supongo que los índices en la matriz A son de base cero, es decir, el primer elemento es A[0], el último es A[A.length-1]. Ahora i cuenta hasta A.length-1, y en el cuerpo del bucle accede a A[i+1], que está fuera de la matriz para la última iteración. O, simplemente, si está comparando cada elemento con el siguiente elemento, solo puede hacer comparaciones de longitud-1.

Si solo desea reportar duplicados una vez, usaría una variable bool firstDuplicate, que está configurada en falso cuando encuentra un duplicado y verdadero cuando el número es diferente al siguiente. Entonces solo reportarías el primer duplicado informando solamente los números duplicados si firstDuplicate es verdadero.

Answer 4

Tu respuesta parece bastante buena. Primero clasificándolos y simplemente revisando los valores vecinos, obtienes O(n log(n)) complejidad que es bastante eficiente.

Merge sort es O(n log(n)) mientras se comprueban los valores vecinos es simplemente O(n).

Sin embargo, una cosa (como se menciona en uno de los comentarios) es que obtendrá un desbordamiento de pila (lol) con su pseudocódigo. El bucle interno debe ser (en Java):

for (int i = 0; i < array.length - 1; i++) { 
    ... 
} 

Entonces también, si realmente desea mostrar qué números (o índices y) son los duplicados, tendrá que guardarlos en una lista separada.

Answer 5

¿Desea encontrar Duplicados en Java?

Puede usar un HashSet.

HashSet h = new HashSet(); 
for(Object a:A){ 
    boolean b = h.add(a); 
    boolean duplicate = !b; 
    if(duplicate) 
     // do something with a; 
} 

El retorno Valor de add() se define como:

cierto si el conjunto no lo hizo ya contienen el elemento especificado.

EDIT: Sé HashSet está optimizado para las inserciones y contiene operaciones.Pero no estoy seguro si es lo suficientemente rápido para sus preocupaciones.

EDIT2: Lo he visto recientemente agregó la etiqueta de la tarea. Yo no prefiero mi respuesta si la tarea de la ITF, ya que puede ser de "alto nivel" para una allgorithm-lección

http://download.oracle.com/javase/1.4.2/docs/api/java/util/HashSet.html#add%28java.lang.Object%29

Answer 6

O (n) algoritmo: atraviesan la matriz y tratar de entrada de cada elemento una tabla hash/set con número como la tecla hash. si no puede ingresar, entonces eso es un duplicado.

Answer 7

public void printDuplicates(int[] inputArray) { 
    if (inputArray == null) { 
     throw new IllegalArgumentException("Input array can not be null"); 
    } 
    int length = inputArray.length; 

    if (length == 1) { 
     System.out.print(inputArray[0] + " "); 
     return; 
    } 

    for (int i = 0; i < length; i++) { 

     if (inputArray[Math.abs(inputArray[i])] >= 0) { 
      inputArray[Math.abs(inputArray[i])] = -inputArray[Math.abs(inputArray[i])]; 
     } else { 
      System.out.print(Math.abs(inputArray[i]) + " "); 
     } 
    } 
}