how do you return number of distinct/unique values in an array for example
int[] a = {1,2,2,4,5,5};
+3
A:
A set stores each unique (as defined by .equals()) element in it only once, and you can use this to simplify the problem. Create a Set (I'd use a HashSet), iterate your array, adding each integer to the Set, then return .size() of the Set.
dcrosta
2009-09-26 21:42:20
Pretty sure a set will have a .size() or .length() or .count() method to get the number of elements in it.
jeffamaphone
2009-09-26 21:43:15
of course, the OP asked for the number of distinct integers, not a list of distinct integers. Same approach applies, though.
Michiel Buddingh'
2009-09-26 21:43:44
Guh. I wrote it that way originally, than re-misread the question. Editied now.
dcrosta
2009-09-26 21:56:19
+5
A:
Set<Integer> s = new HashSet<Integer>();
for (int i : a) s.add(i);
int distinctCount = s.size();
Mehrdad Afshari
2009-09-26 21:43:02
+2
A:
An efficient method: Sort the array with Arrays.sort. Write a simple loop to count up adjacent equal values.
Tom Hawtin - tackline
2009-09-26 21:45:05
+1. This is the best answer since Latoya only asks for number of distinct values.
tulskiy
2009-09-27 03:42:10
I think crosta is generally better as it is easier and is less likely to go wrong. My answer is only if performance of this particular task matters (as ever, for preference measure the simple solution to see if it is comfortably sufficient first).
Tom Hawtin - tackline
2009-09-27 03:56:02
+2
A:
Really depends on the numbers of elements in the array. If you're not dealing with a large amount of integers, a HashSet or a binary tree would probably be the best approach. On the other hand, if you have a large array of diverse integers (say, more than a billion) it might make sense to allocate a 2^32 / 2^8 = 512 MByte byte array in which each bit represents the existence or non-existence of an integer and then count the number of set bits in the end.
A binary tree approach would take n * log n time, while an array approach would take n time. Also, a binary tree requires two pointers per node, so your memory usage would be a lot higher as well. Similar consideration apply to hash tables as well.
Of course, if your set is small, then just use the inbuilt HashSet.
DrJokepu
2009-09-26 21:58:18