Wednesday, March 25, 2015

Print frequency


Given an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter.
For Ex:
Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100]
n -> 2
Out put -> [100, 0] or [100, 2]
Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2


It doesn't look like there are ways (not on top of my mind) that we can avoid extra space. The PriorityQueue I created is fixed to the size of n, and it is a min heap. So each time I poll out the head if it is smaller than the one that is supposed to be put in, and add the new one into the queue. In the end, iterate through the queue and print out all elements in it.


public static void frequencyPrinter(int[] num, int n){
  if(num == null || num.length == 0)
   return;
  Map count = new HashMap ();
  for(int i : num){
   if(!count.containsKey(i))
    count.put(i, 1);
   else
    count.put(i, count.get(i) + 1);
  }
  PriorityQueue> pq = new PriorityQueue> (n, new countComparator());
  for(Entry e : count.entrySet()){
   if(pq.size() < n)
    pq.add(e);
   else{
    if(e.getValue() > pq.peek().getValue()){
     pq.poll();
     pq.offer(e);
    }
   }
  }
  Iterator> it = pq.iterator();
  while(it.hasNext()){
   System.out.println(it.next().toString());
  }
 }
 private static class countComparator implements Comparator>{
  public int compare(Entry a, Entry b){
   return a.getValue() - b.getValue();
  }
 }

No comments:

Post a Comment