Como remover duplicatas de um vetor C ++
'E' ocorre três vezes em posições diferentes. 'A' ocorre duas vezes em posições diferentes. 'C' ocorre duas vezes em posições diferentes. Então, 'e', 'a' e 'c' tem duplicados. Cada um dos demais personagens ocorrem uma vez.
Para remover duplicatas neste vetor, significa remover as duplicatas de 'e', 'a' e 'c' e permitir a primeira ocorrência de cada personagem, em sua posição. O resultado deve ser:
vetorExistem duas maneiras principais de remover duplicatas de um vetor. Uma maneira é o caminho direto ou bruto. Dessa forma, o primeiro elemento é verificado contra o restante dos elementos, e qualquer duplicado é removido. O segundo elemento é verificado contra o restante dos outros elementos à direita, removendo duplicatas. O mesmo procedimento é feito para o terceiro elemento, e o restante dos elementos. Assim geralmente leva muito tempo. A outra maneira é manter o vetor original e ter uma cópia classificada. Remova duplicatas do vetor classificado enquanto faz a cópia de qualquer elemento duplicado, como chave em um mapa. Finalmente, examine o vetor original desde o início ao fim usando o mapa para apagar duplicatas.
Essas duas maneiras podem ser referidas como o método da força bruta e o método de classificação e compra, respectivamente. Este artigo ilustra os dois lados. Não se esqueça de incluir a biblioteca vetorial no início do programa.
Removendo um elemento vetorial
Um elemento vetor. A sintaxe é:
constExPR Erast Erase (posição const_iterator);O argumento é um iterador que aponta para o elemento, a ser removido.
Removendo duplicatas por força bruta
Com essa abordagem, o primeiro elemento é comparado com o restante dos elementos à direita, um por um, e qualquer duplicata é apagada. O segundo elemento, se não foi apagado, é comparado com o restante dos outros elementos à direita, um por um, apagando duplicações. O mesmo procedimento é feito para o terceiro elemento, e o restante dos elementos. Essa abordagem geralmente leva muito tempo. O código a seguir ilustra com iteradores:
vetorvtr = 'e', 'g', 'i', 'e', 'a', 'e', 'c', 'a', 'c';para (Vector :: Iterator Itei = VTR.começar(); Itei
para (Vector :: iterator itej = itei+1; itej
vtr.apagar (itej);
para (int i = 0; i
cout<
Nos parênteses do loop interno.
Removendo duplicatas por classificação
Observe do método acima de que há muita renomação (reler e comparação) da grande sequência, a uma pequena sequência de elementos do One Vector. Se todo o vetor for digitalizado uma ou duas vezes ou três vezes, isso provavelmente significaria menos acessos dos elementos em comparação com a abordagem acima. Bem, todo o vetor pode até ser digitalizado quatro ou mais vezes, mas não muitas vezes. Isso não deve necessariamente ser feito com o mesmo vetor. Isso pode ser feito com cópias do vetor.
Com a segunda abordagem, o vetor original é mantido enquanto uma cópia classificada é feita dele. O vetor classificado é lido (digitalizado), apagando a duplicata de elementos consecutivos que ocorreram mais de uma vez. Um iterador para o loop pode conseguir isso, desde o início até o final do vetor classificado, uma vez através. Enquanto essa leitura e alguma apagamento estão ocorrendo, para qualquer elemento que ocorra mais de uma vez, uma cópia do elemento é feita em um mapa, e o valor correspondente para esta chave é dado o valor -1. Este valor de -1 será alterado para 1 para indicar um duplicado. Cada valor no mapa é um indicador para duplicar de sua chave que pode ocorrer duas ou mais vezes no vetor original.
Se o vetor classificado com duplicatas removidas foi necessário, o vetor classificado será retornado e o trabalho será feito. Se a ordem da primeira ocorrência dos elementos vetoriais tiver que ser mantida, o seguinte subprocedimento deverá ocorrer (continue):
Releia o vetor original desde o início. Ao ler, se uma chave não ocorrer no mapa (mapa retornar 0), permita essa chave no vetor original. Isso significa que a chave não tem duplicado. Se uma chave do vetor original ocorre no mapa, significa que é a primeira ocorrência de duplicatas para esse elemento no vetor. Faça o valor indicador para a chave no mapa, 1. Esse valor indicador agora tem o valor, 1. Continue lendo o restante dos elementos no vetor original e verifique o elemento duplicado com o mapa. Se uma chave for encontrada e o valor da chave do mapa é 1, o elemento atual é uma duplicata. Remova o elemento atual. (Lembre -se de que a primeira ocorrência de uma chave duplicada girou o valor indicador correspondente no mapa de -1 a 1.) Continue dando um valor de 1 para os indicadores da chave do mapa, removendo o elemento vetorial atual original que já possui um 1 correspondente no mapa do vetor original; até o final do vetor original ser alcançado. O vetor original resultante é o vetor sem nenhum elemento duplicado e na ordem com as primeiras ocorrências.
Para codificar mapa em C ++, a biblioteca do mapa (não -ordered_map) deve ser incluída. Como a função Sort () na biblioteca do algoritmo também será usada, a biblioteca de algoritmo também deve ser incluída no programa. O cabeçalho para o programa dessa abordagem deve ser:
#incluir#incluir
#incluir
#incluir
usando namespace std;
O primeiro segmento de código na função principal C ++ pode ser:
vetorvetor
classificar (vtr.BEGIN (), VTR.fim());
UNODERED_MAP
A primeira declaração define o vetor original. A segunda declaração faz uma cópia do vetor original. A terceira declaração classifica o vetor copiado. A quarta declaração declara o mapa, sem inicialização. O próximo segmento de código na função principal C ++ pode ser:
para (vetor :: iterator iter = vtr.começar(); iterif ( *iter0 == *iter1)
mp [*iter1] = -1;
iter--;
vetor :: iterator iter2 = vtr.apagar (iter1);
Este segmento de código apaga as duplicatas do vetor copiado classificado. Enquanto faz isso, cria as entradas do mapa. Observe que, nos parênteses do loop for, a iteração atinge o último elemento, mas um (e não o último elemento). Isso ocorre porque os elementos atuais e os próximos estão envolvidos no código. Observe também que quando um elemento deve ser apagado, o iterador é retardado (decrementado) por um passo.
Se o vetor classificado sem duplicatas for o que era necessário, o código a seguir exibiria o resultado:
para (int i = 0; icout<
VTro.apagar (iter);
iter--;
if (mp [*iter] == -1)
mp [*iter] = 1;
O motivo da escolha, -1 e 1, em vez de 0 e 1, é porque o valor padrão (ausente) deste mapa é 0. Isso evita a confusão com os elementos que não têm duplicado. Um loop comum da seguinte maneira pode imprimir o vetor original final (reduzido):
para (int i = 0; icout<
A saída do programa é:
A C E G IE g i a c
A primeira linha da saída é a entrada classificada sem duplicatas. A segunda linha é a entrada na ordem dada, com as duplicatas removidas.
Conclusão
Para remover duplicatas de um vetor C ++, o método da força bruta pode ser usado. Este método geralmente é lento. O leitor é aconselhado a usar o método de classificação e comparar, que geralmente é rápido, para seu trabalho comercial. Ambos os métodos foram explicados acima.