Given this pseudo-code that finds the number of distinct elements in the given array:
D(A) // A is an array of numbers U_Size = 1 For i=2 to length(A) U=? For j=1 to U_Size If A[j]=A[i] Then U = FALSE j = U_Size if U = TRUE Then U_Size = U_Size +1 A[U_Size] = A[i] return U_Size
Time complexity for that alogrithm is $O(n^2)$
I will need to write 2 new algorithms for the same purpose in $O(n)$ according to one of each of the conditions bellow:
- let's say that the numbers are integers only and inside the range of [$10,10n$], without using any sorting method
- Now, there is no given range of numbers, and I can use any sorting method I want
for the first condition, I tried using HashSet, but I think it has a more sofisticated solution. My pseudo-code:
countDistinctNums(int A, int n) hashSet hs = new Hashset for i=0 to n // add all the elements to the HashSet hs.add(A[i]) // return the size of hashset as it consists of // all unique elements Return hs.size();
for the second one, a hash table will be the optimal solution but I think also one of the linear-sorting methods will be good enough
My questions are:
- Does HashSet is a good solution for one of the conditions ( or both )?
- How do I implement an HashTable for the solution of the second condition?