algorithm - son - que tanto sabes de programacion

¿Qué es un algoritmo eficiente para encontrar un número único en un conjunto de números de 1 millón?

Question

Me han hecho esta pregunta en una entrevista. En 1 millón de números, todos los números tienen un duplicado, excepto un número. ¿Cómo encontrar ese número? ¿Qué algoritmo debo usar para obtener una buena complejidad de tiempo y espacio? Se me ocurrió usar EXOR gate, pero todavía me estoy demorando en implementar eso.

Answer 1

Creo que si combinamos la técnica de búsqueda rápida (búsqueda) y xor, podríamos obtener el código más rápido posible. Sin embargo, lo estoy intentando, pero corrígeme si esta idea está mal mientras tanto.

Por cierto, esto tiene un buen número de casos de uso. Aunque la pregunta es independiente del lenguaje y requiere un algoritmo claro, menciono algunos casos de uso que los lectores pueden encontrar útiles.

Los 0 pueden ser duplicados ... o números negativos ...

System.out.println(33 ^ 33 ^ 7 ^ 0 ^ 0 ^ 5 ^ 7 ^ 5); está dando 0 (0 es un duplicado aquí)

Los duplicados pueden ser más de 2:

System.out.println(1 ^ 1 ^ 2 ^ 3 ^ 3 ^ 3); Está dando 1, en lugar de 2 ...

Y una y otra vez, la pregunta posiblemente sea compleja de lo que pensamos primero.

Answer 2

Lo siguiente puede resolver tu problema:

Complejidad: O(N)

// Assuming the duplicate are going by pair
// x ^x == 0 and x ^0 == x
int find_unique(const std::vector<int>& v)
{
    assert(v.size() % 2 == 1);

    int res = 0;
    for (auto value : v) {
        res ^= value;
    }
    return res;
}

O
Complejidad: O(N log N)

int find_unique(std::vector<int>& v)
{
    if (v.empty()) { throw std::runtime_error("empty vector"); }
    std::sort(v.begin(), v.end());
    auto it = std::unique(v.begin(), v.end());
    if (it == v.begin()) { throw std::runtime_error("no unique number"); }
    if (it != v.begin() + 1) { throw std::runtime_error("several unique numbers"); }
    return v[0];
}

o Complejidad: O(N log N)

int find_unique(std::vector<int>& v)
{
    if (v.empty()) { throw std::runtime_error("empty vector"); }
    if (v.size() == 1) { return v[0]; }
    std::sort(v.begin(), v.end());
    if (v[0] != v[1]) { return v[0]; }

    for (int i = 1, size = v.size(); i + 1 < size; ++i) {
        if (v[i] == v[i - 1]) { continue; }
        if (v[i] == v[i + 1]) { ++i; continue; } // we may skip v[i + 1]
        return v[i];
    }
    return v.back();
}

Answer 3

Otra solución simple: se pueden usar dos conjuntos de bits, uno para marcar la existencia de un número y otro para marcar la duplicación. Recorremos la matriz y marcamos cada elemento para existencia y duplicación. Luego, iteramos a través de los conjuntos de bits para encontrar un número que esté marcado para existir y que no esté marcado para duplicación.

int[] numbers = new int[] { 1, 1, 2, 2, 3, 4, 4, 5, 5 };

    BitSet bs1 = new BitSet();
    BitSet bs2 = new BitSet();

    int largestNumber = 0;

    for (int i = 0; i < numbers.length; i++) {
        int number = numbers[i];
        if (bs1.get(number) == false) {
            // Mark for existence
            bs1.set(number);
        } else {
            // Mark for duplicating
            bs2.set(number);
        }

        if (number > largestNumber) {
            largestNumber = number;
        }
    }

    for (int i = 0; i <= largestNumber; i++) {
        if (bs1.get(i) && !bs2.get(i)) {
            System.out.println("Non duplicating number is:  " + i);
        }
    }

}

Answer 4

Para una gran cantidad de elementos de entrada (a diferencia de los ejemplos con unos pocos números), debería llevar una cantidad de tiempo considerable obtener la entrada en alguna estructura de datos. Estaba pensando en usar este tiempo necesario como parte del proceso de cálculo al ponerlo en un mapa. El valor del mapa solo será uno para el único número. Supongo que los datos son correctos, así que omito la verificación de eso, pero si hay varios números que ocurren solo una vez, solo devolverá el primero.

Debería haber espacio para una mayor optimización, por ejemplo, accediendo al mapa por valor y solo busque el que tiene 1. Creo que esto podría hacerse fácilmente con Boost.Bimap.

int getSingleNumber(){

map<int, int> numbers;

for (all input items)
    {
    numbers[currentInputItem]++;
    }

for( map<int,int>::iterator ii=numbers.begin(); ii!=numbers.end(); ++ii)
{
    if ( (*ii).second == 1 ) return (*ii).first;
}
}

Answer 5

prueba esto

    int[] a = {1, 2, 1, 2, 3};
    Arrays.sort(a);
    for(int i = 0; i < a.length; i++) {
        if (i == 0 && a[i] != a[i + 1] || i == a.length -1 || a[i] != a[i - 1] && a[i] != a[i + 1]) {
            System.out.println(a[i]);
            break;
        }
    }

Answer 6

Usa xor para todos los números secuencialmente.

Para la siguiente lista de números:

1, 2, 3, 4, 3, 2, 1

Sea ^ representa la disyunción exclusiva (o xor )

Entonces,
1 ^ 2 ^ 3 ^ 4 ^ 3 ^ 2 ^ 1 = 4