Jak mogę policzyć unikalne liczby w tablicy bez zmiany rozmieszczenia elementów tablicy?

Question

Mam problemy z zliczaniem unikatowych wartości w tablicy i muszę to zrobić bez zmiany rozmieszczenia elementów tablicy.

Jak mogę to zrobić?

Answer 1

Jeśli masz .NET 3.5 można łatwo osiągnąć z LINQ poprzez:

int numberOfElements = myArray.Distinct().Count(); 

Non LINQ:

List<int> uniqueValues = new List<int>(); 
for(int i = 0; i < myArray.Length; ++i) 
{ 
    if(!uniqueValues.Contains(myArray[i])) 
     uniqueValues.Add(myArray[i]); 
} 
int numberOfElements = uniqueValues.Count; 

Answer 2

To jest o wiele bardziej efektywne wdrożenie non LINQ.

 var array = new int[] { 1, 2, 3, 3, 3, 4 }; 
     // .Net 3.0 - use Dictionary<int, bool> 
     // .Net 1.1 - use Hashtable 
     var set = new HashSet<int>(); 
     foreach (var item in array) { 
      if (!set.Contains(item)) set.Add(item); 
     } 
     Console.WriteLine("There are {0} distinct values. ", set.Count); 

Answer 3

Czy należy liczyć tylko różne wartości lub czy należy liczyć każdą liczbę w tablicy (np. "Numer 5 zawiera 3 razy")?

Drugie wymaganie można spełnić, rozpoczynając kroki algorytmu sortowania zliczania.
To byłoby coś takiego:

• budować zestaw gdzie indeks/klucz jest element należy zaliczyć
• kluczowym jest podłączony do zmiennej, która przechowuje liczbę wystąpień klucza Element
• iteracyjne Array (tablica [indeks])

• wartość przyrostu klucza

Chodzi

Answer 4

wykorzystanie O (n), czas trwania pamięci MAX_VALUE

boolean[] data = new boolean[maxValue]; 
for (int n : list) { 
    if (data[n]) counter++ 
    else data[n] = true; 
}