Need advice - checking values in an array

Jul 2012
Hey all. I have a very simple problem but I need to check what's the best way to handle it.

I need to write an efficient program that gets an array and its length. The program will return the number of different values in the array. Example:
the array is {7, 587 , 1 , 56 , 7 , 12 , 9 , 7 , 1 ,1 } the program will return 6 (because there are six different values. 1,7,9,12,56,587)
The program is allowed to change the values of the array received.

Problem is, efficient is a very ambiguous term. How do I know if my way is the best way? What I'm thinking is maybe sorting the array with quicksort or mergesort, and then iterating through it, counting the times where a[n] != a[n+1]

Anyone has a better idea?


Forum Staff
Nov 2006
UTC -5
There's a literature on this problem. I've actually read a clever algorithm for *estimating* this value in sublinear time, for example. But unless I had special reason to be concerned about it I'd just use the straightforward method you mention.