Bem-vindos todos!
Eu sou Oleg. Especialização: Kernels / drivers / hardware / redes / embarcados C ++ / C / OS. Vivo e trabalho no estrangeiro há cerca de um ano e meio. Agora na Finlândia, antes disso havia a Polônia. Eles me contaram sobre as peculiaridades de se mudar para os dois países antes de mim, quem está interessado - escreva, eu responderei suas perguntas. Muito também foi escrito sobre a vida nesses países. Mas algum dia apresentarei minhas impressões de ambos na forma de um ensaio gratuito.
Agora quero falar sobre um problema que passei meio dia resolvendo, embora não tenha valido a pena. E o engraçado é que resolvi alguns problemas semelhantes em entrevistas. Corri para ela enquanto cavava um dos meus projetos domésticos.
Então, dado um certo número de conjuntos de inteiros de tamanhos diferentes. Você precisa encontrar os números que estão em todos os conjuntos, exceto um. O índice do conjunto onde o elemento está faltando também é necessário.
Suponha que existam conjuntos {1, 2, 3}, {3, 0, 4}, {5}. Neste exemplo artificial, o elemento {3}, que está presente no zero e no primeiro conjuntos e está ausente no segundo, afirma ser um achado. Também pode ser escrito como um conjunto {3, 2}. Literalmente, esse registro é decifrado da seguinte forma: o valor 3 está ausente no conjunto 2. Mais uma condição: participam apenas inteiros positivos de 1 a 64. Os elementos de cada conjunto são únicos.
Fundamentalmente, esse é um tipo de generalização do problema clássico da entrevista. Este último é formulado da seguinte forma: os números são recebidos na entrada de um determinado bloco do programa, é necessário cortar as duplicatas. Isso pode ser resolvido de forma elementar usando a primitiva STL unordered_set. É bom porque tem O (1) - tempo de busca constante para sequências de números curtas. No âmbito de uma tarefa limitada, é bastante agradável para si mesmo em sabor e cor. Além disso, ao adicionar uma duplicata a ele, ele simplesmente não o adicionará. Também não é necessário verificar o valor de retorno nesse caso. Ou seja, salvamos três linhas de código, que de qualquer forma estão contidas na implementação do modelo. Mas, como a gama de números em meu projeto é limitada, você pode passar sem ela. Sim, se você expandir o intervalo de números, então unordered_set, ou algo parecido, terá que ser usado.
Para simplificar, vamos definir o número de conjuntos igual a 3. O conjunto é armazenado em um vetor, ou vetor de modelo STL <vetor>. O resultado é um conjunto de pares de vetores de números não negativos <par <int, int >>. Num par, em primeiro lugar está o próprio elemento, no segundo está o índice do conjunto onde não 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) , ,
Só isso, meio dia de tormento. O código não tem a pretensão de ser bonito. O desejo era apenas apresentar uma ideia, ou uma abordagem para resolver tais problemas. Agradecimentos especiais a Ilyawataru, que recomendou que eu prestasse atenção à otimização dos meus algoritmos.
Link para o código https://yadi.sk/d/F2dLt6v_uvjKdQ