I was trying to solve this question:
Given an array of integers with only 3 unique numbers print the numbers in ascending order (with their respective frequencies) in O(n) time.
I wanted to solve it without using the counting sort
algorithm,
So what I thought is I could just do a for loop
and insert the numbers in a HashMap
and then loop
through the HashMap entrySet
and print the required info.
Here is the function:
public static void printOut(int[] arr){
Map<Integer,Integer> hm=new HashMap<Integer,Integer>();
for(int num : arr){
if(hm.containsKey(num)){
hm.put(num,hm.get(num)+1);
}else{hm.put(num,1);}
}
for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
System.out.println("Key= "+entry.getKey()+" Value= "+entry.getValue());
}
}
which did the trick when I my array was: [3, 3, 2, 1, 3, 2, 1]
However the above array should not lead to any collision so I tried to use an array which should lead to collisions, one of the arrays I tested my function with was: [6,6,9,9,6,3,9]
yet my function still printed the Keys
in ascending order, which got me confused, because I thought when the Key
of the HashMap
is an Integer the hash code should be hashIndex = key % noOfBuckets
so when I have the numbers 6, 9 and 3
as my HashMap keys
I thought there would be collisions and my function should print(based on the above used array):
Key= 6 Value= 3
Key= 9 Value= 3
Key= 3 Value= 1
But instead it printed:
Key= 3 Value= 1
Key= 6 Value= 3
Key= 9 Value= 3
Could anyone please explain to me why I got the right solution to the question I was trying to solve instead of the answer I was expecting?
Thanks.