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.

Cómo obtener las posiciones originales de los elementos en una intersección?

20 Jul, 2023 Programación

Tengo dos vectores que contienen enteros. Puedo obtener la intersección de esos vectores, pero eso solo me da los valores. También quiero saber las posiciones de índice/clave de los elementos originales. ¿Cómo puedo hacer esto? He intentado usar “lower_bound” para buscar en cada vector los elementos de la intersección y encontrar sus posiciones, pero eso es lento. Espero que haya alguna forma inteligente de tal vez usar un comparador personalizado o algo así en “set_intersection” para tener acceso a las claves de cada elemento que se compara, pero no he tenido suerte buscando una forma de hacerlo.

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Una posible solución es crear un std::map<int,int> donde las claves sean los enteros de los vectores y los valores sean sus índices correspondientes. Luego, iterar sobre la intersección de los dos vectores y buscar los índices en el mapa para obtener los índices originales.

    Aquí hay un ejemplo de código:

    “`c++
    #include
    #include

    #include

    std::vector get_intersection(const std::vector& v1, const std::vector& v2)
    {
    std::map<int, int=””> index_map;
    for (int i = 0; i < v1.size(); ++i)
    {
    index_map[v1[i]] = i;
    }

    std::vector intersection;
    for (int i : v2)
    {
    auto it = index_map.find(i);
    if (it != index_map.end())
    {
    intersection.push_back(i);
    // Obtener el índice del mapa
    int index = it->second;
    // Hacer algo con el índice…
    }
    }

    return intersection;
    }

    int main()
    {
    std::vector v1 = {1, 2, 3, 4, 5};
    std::vector     v2 = {1, 3, 5, 7, 9};

    auto intersection = get_intersection(v1, v2);
    // intersection contiene {1, 3, 5}
    return 0;
    }
    “`

    En este ejemplo, creamos un std::map<int,int> llamado index_map y lo poblamos con los valores de v1 como claves y los índices correspondientes como valores. Luego, iteramos sobre v2 y buscamos cada valor en index_map. Si existe, lo agregamos al vector intersection y obtenemos el índice desde el mapa. Ten en cuenta que map::find tiene una complejidad logarítmica, por lo que este método debería ser más rápido que usar lower_bound.</int,int></int,>

    </int,int>

Comments are closed.