Remova duplicatas de uma lista <T> em c #

487

Alguém tem um método rápido para desduplicar uma lista genérica em c #?

JC Grubbs
fonte
4
Você se importa com a ordem dos elementos no resultado? Isso excluirá algumas soluções.
Coronel Panic
Uma solução de uma linha:ICollection<MyClass> withoutDuplicates = new HashSet<MyClass>(inputList);
Harald Coppoolse 13/03/19

Respostas:

227

Talvez você deva considerar o uso de um HashSet .

No link MSDN:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        HashSet<int> evenNumbers = new HashSet<int>();
        HashSet<int> oddNumbers = new HashSet<int>();

        for (int i = 0; i < 5; i++)
        {
            // Populate numbers with just even numbers.
            evenNumbers.Add(i * 2);

            // Populate oddNumbers with just odd numbers.
            oddNumbers.Add((i * 2) + 1);
        }

        Console.Write("evenNumbers contains {0} elements: ", evenNumbers.Count);
        DisplaySet(evenNumbers);

        Console.Write("oddNumbers contains {0} elements: ", oddNumbers.Count);
        DisplaySet(oddNumbers);

        // Create a new HashSet populated with even numbers.
        HashSet<int> numbers = new HashSet<int>(evenNumbers);
        Console.WriteLine("numbers UnionWith oddNumbers...");
        numbers.UnionWith(oddNumbers);

        Console.Write("numbers contains {0} elements: ", numbers.Count);
        DisplaySet(numbers);
    }

    private static void DisplaySet(HashSet<int> set)
    {
        Console.Write("{");
        foreach (int i in set)
        {
            Console.Write(" {0}", i);
        }
        Console.WriteLine(" }");
    }
}

/* This example produces output similar to the following:
 * evenNumbers contains 5 elements: { 0 2 4 6 8 }
 * oddNumbers contains 5 elements: { 1 3 5 7 9 }
 * numbers UnionWith oddNumbers...
 * numbers contains 10 elements: { 0 2 4 6 8 1 3 5 7 9 }
 */
Jason Baker
fonte
11
seu inacreditável rápido ... 100.000 strings com List leva 400s e 8MB de RAM, minha própria solução leva 2.5s e 28MB, hashset leva 0.1s !!! e 11MB de ram
sasjaq 25/03
3
HashSet não possui um índice , portanto, nem sempre é possível usá-lo. Eu tenho que criar uma vez uma lista enorme sem duplicatas e usá-lo ListViewno modo virtual. Foi super rápido fazer o HashSet<>primeiro e depois convertê-lo em um List<>(assim é ListViewpossível acessar itens por índice). List<>.Contains()é muito lento.
Sinatr 31/07
58
Ajudaria se houvesse um exemplo de como usar um hashset nesse contexto específico.
Nathan McKaskle
23
Como isso pode ser considerado uma resposta? É um link
mcont 4/15/15
2
O HashSet é ótimo na maioria das circunstâncias. Mas se você tiver um objeto como o DateTime, ele será comparado por referência e não por valor; portanto, você ainda terá duplicatas.
Jason McKindly
813

Se você estiver usando o .Net 3+, poderá usar o Linq.

List<T> withDupes = LoadSomeData();
List<T> noDupes = withDupes.Distinct().ToList();
Fator Místico
fonte
14
Esse código falhará como .Distinct () retorna um IEnumerable <T>. Você precisa adicionar .ToList () a ele.
ljs 6/09/08
Essa abordagem pode ser usada apenas para lista com valores simples.
Polaris
20
Não, ele funciona com listas contendo objetos de qualquer tipo. Mas você terá que substituir o comparador padrão para seu tipo. Assim: public override bool Equals (object obj) {...}
BaBu 09/12/2010
1
É sempre uma boa idéia substituir ToString () e GetHashCode () por suas classes para que esse tipo de coisa funcione.
B Sete
2
Você também pode usar o pacote MoreLinQ Nuget que possui um método de extensão .DistinctBy (). Bastante útil.
Yu_ominae 16/05
178

E se:

var noDupes = list.Distinct().ToList();

No .net 3.5?

ljs
fonte
Duplica a lista?
darkgaze
1
@darkgaze isso apenas cria outra lista com apenas entradas exclusivas. Portanto, todas as duplicatas serão removidas e você ficará com uma lista em que cada posição tem um objeto diferente.
Hexagod #
Isso funciona para a lista de itens da lista em que os códigos dos itens são duplicados e precisam obter uma lista exclusiva
venkat 19/01
90

Basta inicializar um HashSet com uma lista do mesmo tipo:

var noDupes = new HashSet<T>(withDupes);

Ou, se você deseja que uma lista seja retornada:

var noDupsList = new HashSet<T>(withDupes).ToList();
Even Mien
fonte
3
... e se você precisar List<T>usar como resultadonew HashSet<T>(withDupes).ToList()
Tim Schmelter
47

Classifique-o e marque dois e dois ao lado do outro, pois as duplicatas se agruparão.

Algo assim:

list.Sort();
Int32 index = list.Count - 1;
while (index > 0)
{
    if (list[index] == list[index - 1])
    {
        if (index < list.Count - 1)
            (list[index], list[list.Count - 1]) = (list[list.Count - 1], list[index]);
        list.RemoveAt(list.Count - 1);
        index--;
    }
    else
        index--;
}

Notas:

  • A comparação é feita de trás para frente, para evitar a necessidade de recorrer à lista após cada remoção
  • Este exemplo agora usa tuplas de valor em C # para fazer a troca, substitua pelo código apropriado se você não puder usá-lo
  • O resultado final não é mais classificado
Lasse V. Karlsen
fonte
1
Se não me engano, a maioria das abordagens mencionadas acima são apenas abstrações dessas mesmas rotinas, certo? Eu teria adotado sua abordagem aqui, Lasse, porque é como eu imagino mentalmente a movimentação dos dados. Mas agora estou interessado em diferenças de desempenho entre algumas das sugestões.
22110 Ian Ian Hughes
7
Implementá-los e cronometrá-los, única maneira de ter certeza. Mesmo a notação Big-O não o ajudará com métricas de desempenho reais, apenas um relacionamento com efeito de crescimento.
Lasse V. Karlsen
1
Eu gosto dessa abordagem, é mais portátil para outros idiomas.
Jerry Liang
10
Não faça isso. É super lento. RemoveAté uma operação muito cara em umList
Clément
1
Clément está certo. Uma maneira de recuperar isso seria envolvê-lo em um método que gera com um enumerador e retorna apenas valores distintos. Como alternativa, você pode copiar valores para uma nova matriz ou lista.
JHubbard80
33

Eu gosto de usar este comando:

List<Store> myStoreList = Service.GetStoreListbyProvince(provinceId)
                                                 .GroupBy(s => s.City)
                                                 .Select(grp => grp.FirstOrDefault())
                                                 .OrderBy(s => s.City)
                                                 .ToList();

Eu tenho esses campos na minha lista: Id, StoreName, City, PostalCode Eu queria mostrar a lista de cidades em um menu suspenso que possui valores duplicados. solução: agrupe por cidade e escolha o primeiro da lista.

Espero que ajude :)

Eric
fonte
31

Funcionou para mim. simplesmente use

List<Type> liIDs = liIDs.Distinct().ToList<Type>();

Substitua "Type" pelo tipo desejado, por exemplo, int.

Hossein Sarshar
fonte
1
Distinct está no Linq, não System.Collections.Generic, conforme relatado pela página do MSDN.
Almo
5
Esta resposta (2012) parece ser a mesma de duas outras respostas nesta página que são de 2008?
Jon Schneider
23

Como o kronoz disse no .Net 3.5, você pode usar Distinct().

No .Net 2 você pode imitá-lo:

public IEnumerable<T> DedupCollection<T> (IEnumerable<T> input) 
{
    var passedValues = new HashSet<T>();

    // Relatively simple dupe check alg used as example
    foreach(T item in input)
        if(passedValues.Add(item)) // True if item is new
            yield return item;
}

Isso pode ser usado para desduplicar qualquer coleção e retornará os valores na ordem original.

Normalmente, é muito mais rápido filtrar uma coleção (como ambos Distinct()e esta amostra) do que seria remover itens dela.

Keith
fonte
O problema dessa abordagem é que ela é O (N ^ 2), ao contrário de um hashset. Mas pelo menos é evidente o que está fazendo.
Tamas Czinege 29/01/09
1
@DrJokepu - na verdade, eu não percebi que o HashSetconstrutor foi deduplicado, o que o torna melhor para a maioria das circunstâncias. No entanto, isso preservaria a ordem de classificação, que HashSetnão é.
Keith
1
HashSet <T> foi introduzido em 3,5
Thorn
1
@ espinho realmente? Tão difícil de acompanhar. Nesse caso, você poderia usar apenas uma Dictionary<T, object>vez, substituir .Containscom .ContainsKeye .Add(item)com.Add(item, null)
Keith
@ Keith, conforme meu teste HashSetpreserva a ordem, enquanto Distinct()não.
Dennis T --Reinstate Monica--
13

Um método de extensão pode ser uma maneira decente de seguir ... algo como isto:

public static List<T> Deduplicate<T>(this List<T> listToDeduplicate)
{
    return listToDeduplicate.Distinct().ToList();
}

E então chame assim, por exemplo:

List<int> myFilteredList = unfilteredList.Deduplicate();
Geoff Taylor
fonte
11

Em Java (presumo que o C # seja mais ou menos idêntico):

list = new ArrayList<T>(new HashSet<T>(list))

Se você realmente deseja alterar a lista original:

List<T> noDupes = new ArrayList<T>(new HashSet<T>(list));
list.clear();
list.addAll(noDupes);

Para preservar a ordem, basta substituir o HashSet por LinkedHashSet.

Tom Hawtin - linha de orientação
fonte
5
em C #, seria: List <T> noDupes = new List <T> (novo HashSet <T> (lista)); list.Clear (); list.AddRange (noDupes);
smohamed
Em C #, é mais fácil desta maneira: var noDupes = new HashSet<T>(list); list.Clear(); list.AddRange(noDupes);:)
Nawfal
10

Isso leva distintos (os elementos sem duplicar elementos) e converte-os em uma lista novamente:

List<type> myNoneDuplicateValue = listValueWithDuplicate.Distinct().ToList();
Alfred Udah
fonte
9

Use o método Union do Linq .

Nota: Esta solução não requer conhecimento do Linq, além do que existe.

Código

Comece adicionando o seguinte ao topo do seu arquivo de turma:

using System.Linq;

Agora, você pode usar o seguinte para remover duplicatas de um objeto chamado obj1:

obj1 = obj1.Union(obj1).ToList();

Nota: Renomeie obj1para o nome do seu objeto.

Como funciona

  1. O comando União lista uma de cada entrada de dois objetos de origem. Como obj1 são os dois objetos de origem, isso reduz o obj1 a uma de cada entrada.

  2. O ToList()retorna uma nova lista. Isso é necessário, porque os comandos do Linq Unionretornam o resultado como um resultado IEnumerable em vez de modificar a lista original ou retornar uma nova lista.

WonderWorker
fonte
7

Como método auxiliar (sem Linq):

public static List<T> Distinct<T>(this List<T> list)
{
    return (new HashSet<T>(list)).ToList();
}
Conceder
fonte
Eu acho que Distinct já está sendo usado. Além disso (se você renomear o método), ele deve funcionar.
Andreas Reiff
6

Se você não se preocupam com a ordem que você pode apenas empurrar os itens em um HashSet, se você não quiser manter a ordem que você pode fazer algo como isto:

var unique = new List<T>();
var hs = new HashSet<T>();
foreach (T t in list)
    if (hs.Add(t))
        unique.Add(t);

Ou a maneira Linq:

var hs = new HashSet<T>();
list.All( x =>  hs.Add(x) );

Edit: O HashSetmétodo é O(N)tempo e O(N)espaço ao classificar e, em seguida, tornar único (como sugerido por @ lassevk e outros) é O(N*lgN)tempo e O(1)espaço, então não está tão claro para mim (como era à primeira vista) que a forma de classificação é inferior (minha desculpas pelo voto temporário encerrado ...)

Motti
fonte
6

Aqui está um método de extensão para remover duplicatas adjacentes in situ. Chame Sort () primeiro e passe no mesmo IComparer. Isso deve ser mais eficiente que a versão de Lasse V. Karlsen, que chama RemoveAt repetidamente (resultando em vários movimentos da memória do bloco).

public static void RemoveAdjacentDuplicates<T>(this List<T> List, IComparer<T> Comparer)
{
    int NumUnique = 0;
    for (int i = 0; i < List.Count; i++)
        if ((i == 0) || (Comparer.Compare(List[NumUnique - 1], List[i]) != 0))
            List[NumUnique++] = List[i];
    List.RemoveRange(NumUnique, List.Count - NumUnique);
}
gary
fonte
5

Instalando o pacote MoreLINQ via Nuget, você pode facilmente distinguir a lista de objetos por uma propriedade

IEnumerable<Catalogue> distinctCatalogues = catalogues.DistinctBy(c => c.CatalogueCode); 
dush88c
fonte
3

Pode ser mais fácil simplesmente garantir que duplicatas não sejam adicionadas à lista.

if(items.IndexOf(new_item) < 0) 
    items.add(new_item)
Chris
fonte
1
Atualmente, estou fazendo isso assim, mas quanto mais entradas você tiver, maior será a verificação de duplicatas.
Robert Strauch
Eu tenho o mesmo problema aqui. Estou usando o List<T>.Containsmétodo todas as vezes, mas com mais de 1.000.000 de entradas. Esse processo atrasa meu aplicativo. Estou usando uma List<T>.Distinct().ToList<T>()primeira vez.
precisa saber é o seguinte
Esse método é muito lento
darkgaze
3

Você pode usar o Union

obj2 = obj1.Union(obj1).ToList();
flagamba
fonte
7
Explicação por que ele iria trabalhar com certeza gostaria de fazer esta resposta melhor
Igor B
2

Outra maneira no .Net 2.0

    static void Main(string[] args)
    {
        List<string> alpha = new List<string>();

        for(char a = 'a'; a <= 'd'; a++)
        {
            alpha.Add(a.ToString());
            alpha.Add(a.ToString());
        }

        Console.WriteLine("Data :");
        alpha.ForEach(delegate(string t) { Console.WriteLine(t); });

        alpha.ForEach(delegate (string v)
                          {
                              if (alpha.FindAll(delegate(string t) { return t == v; }).Count > 1)
                                  alpha.Remove(v);
                          });

        Console.WriteLine("Unique Result :");
        alpha.ForEach(delegate(string t) { Console.WriteLine(t);});
        Console.ReadKey();
    }
Bhasin
fonte
2

Há muitas maneiras de resolver - a questão das duplicatas na lista, abaixo é uma delas:

List<Container> containerList = LoadContainer();//Assume it has duplicates
List<Container> filteredList = new  List<Container>();
foreach (var container in containerList)
{ 
  Container duplicateContainer = containerList.Find(delegate(Container checkContainer)
  { return (checkContainer.UniqueId == container.UniqueId); });
   //Assume 'UniqueId' is the property of the Container class on which u r making a search

    if(!containerList.Contains(duplicateContainer) //Add object when not found in the new class object
      {
        filteredList.Add(container);
       }
  }

Felicidades Ravi Ganesan

Ravi Ganesan
fonte
2

Aqui está uma solução simples que não requer nenhum LINQ difícil de ler ou qualquer classificação prévia da lista.

   private static void CheckForDuplicateItems(List<string> items)
    {
        if (items == null ||
            items.Count == 0)
            return;

        for (int outerIndex = 0; outerIndex < items.Count; outerIndex++)
        {
            for (int innerIndex = 0; innerIndex < items.Count; innerIndex++)
            {
                if (innerIndex == outerIndex) continue;
                if (items[outerIndex].Equals(items[innerIndex]))
                {
                    // Duplicate Found
                }
            }
        }
    }
David J.
fonte
Você tem mais controle sobre itens duplicados com esse método. Ainda mais se você tiver um banco de dados para atualizar. Para o innerIndex, por que não começar de outerIndex + 1 em vez de começar todas as vezes?
Nolmë Informatique
2

A resposta de David J. é um bom método, sem necessidade de objetos extras, classificação, etc. No entanto, pode ser aprimorado:

for (int innerIndex = items.Count - 1; innerIndex > outerIndex ; innerIndex--)

Portanto, o loop externo fica no topo da parte inferior da lista inteira, mas o loop interno fica no fundo "até que a posição do loop externo seja atingida".

O loop externo assegura que toda a lista seja processada, o loop interno encontra as duplicatas reais, elas só podem acontecer na parte que o loop externo ainda não processou.

Ou, se você não quiser fazer de baixo para cima para o loop interno, poderá iniciar o loop interno em outerIndex + 1.

Hóspede
fonte
2

Todas as respostas copiam listas, ou criam uma nova lista, ou usam funções lentas, ou são extremamente lentas.

Na minha opinião, esse é o método mais rápido e mais barato que conheço (também apoiado por um programador muito experiente, especializado em otimização física em tempo real).

// Duplicates will be noticed after a sort O(nLogn)
list.Sort();

// Store the current and last items. Current item declaration is not really needed, and probably optimized by the compiler, but in case it's not...
int lastItem = -1;
int currItem = -1;

int size = list.Count;

// Store the index pointing to the last item we want to keep in the list
int last = size - 1;

// Travel the items from last to first O(n)
for (int i = last; i >= 0; --i)
{
    currItem = list[i];

    // If this item was the same as the previous one, we don't want it
    if (currItem == lastItem)
    {
        // Overwrite last in current place. It is a swap but we don't need the last
       list[i] = list[last];

        // Reduce the last index, we don't want that one anymore
        last--;
    }

    // A new item, we store it and continue
    else
        lastItem = currItem;
}

// We now have an unsorted list with the duplicates at the end.

// Remove the last items just once
list.RemoveRange(last + 1, size - last - 1);

// Sort again O(n logn)
list.Sort();

O custo final é:

nlogn + n + nlogn = n + 2nlogn = O (nlogn), o que é bastante agradável.

Nota sobre o RemoveRange: Como não podemos definir a contagem da lista e evitar o uso das funções Remover, não sei exatamente a velocidade dessa operação, mas acho que é a maneira mais rápida.

olhar escuro
fonte
2

Se você tem aulas de reboque Producte Customerqueremos remover itens duplicados da lista

public class Product
{
    public int Id { get; set; }
    public string ProductName { get; set; }
}

public class Customer
{
    public int Id { get; set; }
    public string CustomerName { get; set; }

}

Você deve definir uma classe genérica no formulário abaixo

public class ItemEqualityComparer<T> : IEqualityComparer<T> where T : class
{
    private readonly PropertyInfo _propertyInfo;

    public ItemEqualityComparer(string keyItem)
    {
        _propertyInfo = typeof(T).GetProperty(keyItem, BindingFlags.GetProperty | BindingFlags.Instance | BindingFlags.Public);
    }

    public bool Equals(T x, T y)
    {
        var xValue = _propertyInfo?.GetValue(x, null);
        var yValue = _propertyInfo?.GetValue(y, null);
        return xValue != null && yValue != null && xValue.Equals(yValue);
    }

    public int GetHashCode(T obj)
    {
        var propertyValue = _propertyInfo.GetValue(obj, null);
        return propertyValue == null ? 0 : propertyValue.GetHashCode();
    }
}

Você pode remover itens duplicados da sua lista.

var products = new List<Product>
            {
                new Product{ProductName = "product 1" ,Id = 1,},
                new Product{ProductName = "product 2" ,Id = 2,},
                new Product{ProductName = "product 2" ,Id = 4,},
                new Product{ProductName = "product 2" ,Id = 4,},
            };
var productList = products.Distinct(new ItemEqualityComparer<Product>(nameof(Product.Id))).ToList();

var customers = new List<Customer>
            {
                new Customer{CustomerName = "Customer 1" ,Id = 5,},
                new Customer{CustomerName = "Customer 2" ,Id = 5,},
                new Customer{CustomerName = "Customer 2" ,Id = 5,},
                new Customer{CustomerName = "Customer 2" ,Id = 5,},
            };
var customerList = customers.Distinct(new ItemEqualityComparer<Customer>(nameof(Customer.Id))).ToList();

esse código remove itens duplicados por Idse você deseja remover itens duplicados por outra propriedade, você pode alterar o nameof(YourClass.DuplicateProperty) mesmo nameof(Customer.CustomerName)e remover itens duplicados por CustomerNamePropriedade.

Reza Jenabi
fonte
1
  public static void RemoveDuplicates<T>(IList<T> list )
  {
     if (list == null)
     {
        return;
     }
     int i = 1;
     while(i<list.Count)
     {
        int j = 0;
        bool remove = false;
        while (j < i && !remove)
        {
           if (list[i].Equals(list[j]))
           {
              remove = true;
           }
           j++;
        }
        if (remove)
        {
           list.RemoveAt(i);
        }
        else
        {
           i++;
        }
     }  
  }
Paul Richards
fonte
1

Uma implementação intuitiva simples:

public static List<PointF> RemoveDuplicates(List<PointF> listPoints)
{
    List<PointF> result = new List<PointF>();

    for (int i = 0; i < listPoints.Count; i++)
    {
        if (!result.Contains(listPoints[i]))
            result.Add(listPoints[i]);
        }

        return result;
    }
Moctar Haiz
fonte
Este método também é lento. Cria uma nova lista.
darkgaze