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

Question

I'm having trouble counting unique values ​​in an array, and I need to do this without rearranging the elements of the array.

How can i do this?

Answer 1

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

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

Not 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 much more efficient implementation without 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

O (n) max_value memory usage time

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

Answer 4

Should only individual values ​​be taken into account, or should each number in the array be counted (for example, "number 5 is contained 3 times")?

The second requirement can be fulfilled with the initial steps of the counting sorting algorithm.
It will be something like this:

• build a set in which the index / key is the item to be counted
• the key is associated with a variable that contains the number of occurrences of the key element
• array iteration
  • key increment value (array [index])

Hi