TOP K Frequent elements in an unsorted array

Given an unsorted array, count its frequency, output its top k frequent elements

Solution1:
Use HashMap + TreeMap with customized comparator

import java.util.*;

class ValueComparator implements Comparator {
    Map base;
    public ValueComparator(Map base) {
        this.base = base;
    }
    public int compare(Integer a, Integer b) {
        if(base.get(a) >= base.get(b)) {
            return -1;
        } else {
            return 1;
        }
    }
}

class topk{
    public static void main(String[] args) {
        HashMap map = new HashMap();
        ValueComparator cmp =  new ValueComparator(map);
        TreeMap res = new TreeMap(cmp);

        int[] A = {1,2,1,3,4,2,5};
        for(int a : A){
            if(map.containsKey(a)) {
                map.put(a, map.get(a)+1);
            } else {
                map.put(a,1);
            }
        }

        System.out.println("unsorted: "+map);
        res.putAll(map);
        
        System.out.println("sorted: "+res);
    }
}

Solution2:
Use HashMap + MinHeap with customized comparator

import java.util.*;

//minheap + hashmap

class topK1{
public static int[] findtopK(int[] arr, int k) {
HashMap map = new HashMap();
for(int a: arr) {
if(map.containsKey(a)) {
map.put(a, map.get(a)+1); 
} else {
map.put(a,1);
}
}
//construct a minheap
Comparator cmp = new Comparator() {
	public int compare(Integer e1, Integer e2) {
		return map.get((int)e1) - map.get((int)e2);
	} 
};

PriorityQueue minheap = new PriorityQueue(k,cmp);

Iterator iterator = map.keySet().iterator();
while(iterator.hasNext()) {
	Integer iter = iterator.next();
	System.out.println(iter);
	if(minheap.size() < k) {
		minheap.add((int)iter);
	} else {
		if(map.get(minheap.peek())< map.get((int)iter)) {
			minheap.poll();
			minheap.add((int)iter);
		} else {
			continue;
		}
	}
	System.out.println(iter+"   "+map.get(iter)+"   "+minheap.peek());
}

int[] sol = new int[k];
for(int i=0;i<k;i++) {
	sol[i] = minheap.poll();
}
System.out.println();
return sol;
}

public static void main(String[] args) {
	int[] arr = findtopK(new int[]{1,1,1,1,3,3,3,2,2,4,5},3);
	for(int i: arr) {
		System.out.print(i+"  ");
	}
}
}
Output: 2,3,1

Attention:
Minheap for key based on its value
1. don’t write Comparator cmp instead of Comparator cmp
2. don’t mess up with Maxheap

HashMap map = new HashMap();
Comparator cmp = new Comparator() {
	public int compare(Integer e1, Integer e2) {
		return map.get((int)e1) - map.get((int)e2);
	} 
};
PriorityQueue minheap = new PriorityQueue(k,cmp);

Iterator:
1. declare

Iterator iterator = map.keySet().iterator();
Integer iter = iterator.next();
Iterator iterator = map.keySet().iterator();
while(iterator.hasNext()) {
	Integer iter = iterator.next();
	System.out.println(iter);
	if(minheap.size() < k) {
		minheap.add((int)iter);
	} else {
		if(map.get(minheap.peek())< map.get((int)iter)) {
			minheap.poll();
			minheap.add((int)iter);
		} else {
			continue;
		}
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s