Bueno, suponga que le dan el siguiente problema:

Tiene una lista desordenada de números de tamaño N; Cada elemento puede estar entre 0 y N. Le preguntan cual es la forma más rápida de saber si dicha lista tiene elementos duplicados, utilizando la menor cantidad de memoria posible y en un tiempo constante.

¿Como lo resolvería usted?

Usted podría comenzar resolviendo este problema contando cuantas ocurrencias de cada número aparecen en la lista. Para ello podría guardarlas en un arreglo asociativo (HashMap) el cual tiene tiempo de accesso constante. Pero el problema es que si usted tiene muchisimos números repetidos, entonces va a gastar memoria que jode…

Bueno, si alguna vez usted vió corrimiento de bits ala izquierda y mascaras de bits (en la ULA yo lo aprendí a hacer en una materia que se llama sistemas lógicos :)) entonces vera que el algoritmo se puede simplificar bastante simplemente dandole una mascara distinta a cada número, guardandolos a todos en una variable entera. Si recuerda bien, cada vez que corremos un bit a la izquierda es como si estuvieramos elevando a la n dicho número, donde n es la cantidad de bits que corremos a la izquierda.

¿Fumado? Si, pero el concepto es muy arrecho 😀

OK, no siga leyendo, pienselo un rato y vaya al frente de su computadora.

¿Ya terminó?, Veamos entonces el código en Java:

   1:/**
   2: * You are given a list of numbers from 0..N; Each element on the array has
   3: * a number that goes from 0..N. Find if the array has any duplicates on it.
   4: * Well, for this problem I'm going to assume that CPU power is not an issue
   5: * but storage space. Also will try to keep access to the list to the minimun.
   6: *
   7: * @author Jose V Nunez Zuleta
   8: * @version 0.1 - 02/28/2005
   9: * License: GPL
  10: * Blog: El Angel Negro - http://elangelnegro.blogspot.com
  11: */
  12:public class ArrayDuplicate {
  13:    
  14:        /**
  15:         * So the idea is to count how many ocurrences of the number appears.
  16:         * We have to scan the whole list in order to find duplicates, so the
  17:         * worst case is log(n). We will use the fact that each number can be
  18:         * stored as a mask of bits, and based on the position from 0 to N we 
  19:         * can have each number as f(n)=2^(n-1). We are only interested to see 
  20:         * if there is a duplicate, so we don't really care about the real number
  21:         * of duplicates.
  22:         *
  23:         * @param args - List of unsorted numbers
  24:         * @throws Exception if the numbers are invalid
  25:         * @since 0.1
  26:         */
  27:        public static void main(String [] args) throws Exception {
  28:                if (args == null) {
  29:                        throw new
  30:                                IllegalArgumentException("Provide some numbers");
  31:                }
  32:            
  33:                if (args.length == 0) {
  34:                        throw new
  35:                                IllegalArgumentException("Provide some numbers");
  36:                }
  37:                int len = args.length;
  38:            
  39:                int num = 0;
  40:                int checksum = 0;
  41:                for (int i = 0; i < len; i++) {
  42:                        num = Integer.parseInt(args[i]);
  43:                        int mask = numMask(num);
  44:                        // This number is not on the list, so add it!
  45:                        if ( (checksum & mask) == 0 ) {
  46:                                checksum |= mask;
  47:                        } else {
  48:                                System.out.println("Found first duplicate: "
  49:                                        + num);
  50:                                        break;
  51:                        }
  52:                }
  53:        }
  54:    
  55:        /**
  56:         * f(n)=2^(n-1)
  57:         * @param number
  58:         * @return int
  59:         */
  60:        public static int numMask(int number) {
  61:                return 1 << number;
  62:        }
  63:    
  64:}

Una corrida de ejemplo:

[josevnz@localhost Arrays]$ javac ArrayDuplicate.java -d .
[josevnz@localhost Arrays]$ java ArrayDuplicate 2 3 5 8 7 8 90
Found first duplicate: 8
[josevnz@localhost Arrays]$ java ArrayDuplicate 2 3 5 100 7 8 90 2
Found first duplicate: 2
[josevnz@localhost Arrays]$ java ArrayDuplicate 2 3 5 100 7 8 90 0
[josevnz@localhost Arrays]$

Puede bajarse el código desde acá.

¿Se le ocurre otra idea de como ver si hay duplicados?