¡Todos bienvenidos!
Soy Oleg. Especialización: kernels C ++ / C / OS / drivers / hardware / networks / embedded. Vivo y trabajo en el extranjero desde hace aproximadamente un año y medio. Ahora en Finlandia, antes de eso estaba Polonia. Me contaron las peculiaridades de mudarse a ambos países antes que yo, quién está interesado - escribe, responderé tus preguntas. También se ha escrito mucho sobre la vida en estos países. Pero algún día presentaré mis impresiones de ambos en forma de ensayo gratuito.
Ahora les quiero hablar de un problema que pasé medio día resolviendo, aunque no valió la pena. Y lo curioso es que resolví algunos problemas similares durante las entrevistas. Me encontré con ella mientras excavaba uno de los proyectos de mi casa.
Entonces, dado un cierto número de conjuntos de números enteros de diferentes tamaños. Necesita encontrar los números que están en todos los conjuntos excepto uno. También se requiere el índice del conjunto donde falta el elemento.
Suponga que hay conjuntos {1, 2, 3}, {3, 0, 4}, {5}. En este ejemplo artificial, el elemento {3}, que está presente en el primer y cero conjuntos y está ausente en el segundo, pretende ser un hallazgo. También se puede escribir como un conjunto {3, 2}. Literalmente, este registro se descifra de la siguiente manera: el valor 3 está ausente en el conjunto 2. Una condición más: solo participan números enteros positivos del 1 al 64. Los elementos de cada conjunto son únicos.
Básicamente, se trata de una especie de generalización de la tarea clásica de las entrevistas. Este último se formula de la siguiente manera: los números se reciben a la entrada de un determinado bloque del programa, es necesario cortar los duplicados. Se puede resolver de forma elemental utilizando la primitiva STL unordered_set. Es bueno porque tiene O (1) tiempo de búsqueda constante para secuencias de números cortas. En el marco de una tarea limitada, es bastante agradable a sí mismo en sabor y color. Además, al agregarle un duplicado, simplemente no lo agregará. Tampoco es necesario verificar el valor de retorno en ese caso. Es decir, tenemos un ahorro de tres líneas de código, que de todas formas están contenidas en la implementación de la plantilla. Pero, dado que mi proyecto tiene un rango limitado de números, puede prescindir de él. Sí, si expande el rango de números, tendrá que usar unordered_set, o algo por el estilo.
Para simplificar, establezcamos el número de conjuntos igual a 3. El conjunto se almacena en un vector, o vector de plantilla STL <vector>. El resultado es un conjunto de pares de números no negativos vector <pair <int, int >>. En un par, en primer lugar está el elemento en sí, en el segundo está el índice del conjunto donde no está.
void PrepareData(const vector<vector<int> >& src, vector<pair<int, int> >& res)
{
vector<pair<int, int> > data(MAX); //
for(unsigned i(0); i < src.size(); ++i)
{
const auto& rf(src[i]);
for(unsigned j(0); j < rf.size(); ++j)
{
ASSERT(((0 < rf[j]) && (MAX > rf[j])) && "!!! An invalid data !!!");
++data[rf[j]].first; //
data[rf[j]].second += i; //
}
}
auto fs(((src.size() - 1) * src.size()) >> 1); //
for(unsigned i(0); i < data.size(); ++i) //
{
if(data[i].first == src.size() - 1) //
{
pair<int, int> cur{i, 0}; //
cur.second = fs - data[i].second; // ,
res.push_back(cur);
}
}
}1)
2) . . , .
3) data . , , ,
4) , (a[1] + a[n]) * n / 2
5) , ,
6) , ,
Eso es todo, medio día de tormento. El código no pretende ser hermoso. El único deseo era presentar una idea o un enfoque para resolver tales problemas. Un agradecimiento especial a Ilyawataru, quien me recomendó que preste atención a la optimización de mis algoritmos.
Enlace al código https://yadi.sk/d/F2dLt6v_uvjKdQ