Jak policzyć unikatowe liczby w tablicy bez zmiany układu elementów tablicy?

Jeśli masz .NET 3.5, możesz to łatwo osiągnąć dzięki LINQ poprzez:

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

Numery 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;

Jest to znacznie bardziej wydajna implementacja bez 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);

O (n) wykorzystanie pamięci max_value w czasie wykonywania

boolean[] data = new boolean[maxValue];

for (int n : list) {

 if (data[n]) counter++

 else data[n] = true;

}

Czy należy liczyć tylko pojedyncze wartości, czy też należy policzyć każdą liczbę w tablicy (na przykład „liczba 5 zawiera się 3 razy”)?
Drugie wymaganie można spełnić w początkowych krokach algorytmu zliczania sortowania.

To byłoby coś takiego:

• zbuduj zestaw, w którym znajduje się indeks/klucz element do zliczenia
• klucz jest powiązany ze zmienną, która zawiera liczbę wystąpień kluczowy element
• iteracja tablicy [list][*]zwiększanie wartości klucza (tablica [indeks])

[/*]
[/list]
z szacunkiem