Question :
Write code to sort an integer array of size N which has only three unique values 0,1,2 duplicated & randomly placed over the entire array.
- Memory used should be O(1)
- Run time should be O(N)
Solution
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class SortArray2 {
public static void main(String[] args) {
int[] a= { 1, 2, 1, 2, 0, 1, 2, 0, 0, 2, 1, 0 };
int[] r=sort(a);
System.out.println(Arrays.toString(r));
}
public static int[] sort(int[] a)
{
int index=0;
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0;i<a.length;i++)
{
map.put(a[i], (map.getOrDefault(a[i], 0))+1);
}
System.out.println(map);
int i=0;
while(i<=2)
{
for(int j=1;j<=map.get(i);j++)
{
a[index++]=i;
}
i++;
}
return a;
}
}
Post a Comment