How can I count the unique numbers in an array without rearranging the array elements?

Question

I am having trouble counting the unique values in an array, and I need to do so without rearranging the array elements.

How can I accomplish this?

Answer 1

If you have .NET 3.5 you can easily achieve this with LINQ via:

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

This is a far more efficient non LINQ implementation.

        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

Should only the distinct values be counted or should each number in the array be counted (e.g. "number 5 is contained 3 times")?

The second requirement can be fulfilled with the starting steps of the counting sort algorithm.
It would be something like this:

• build a set where the index/key is the element to be counted
• a key is connected to a variable which holds the number of occurences of the key element
• iterate the array
  • increment value of key(array[index])

Regards

Answer 4

O(n) running time max_value memory usage

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