java - TopScore or FilteringMap map, sorted on key -
for lack of better name, calling data structure looking "topscoremap". here requirement. first, size of map fixed. instance, map needs retain top n entries thrown @ map. top n in terms of keys. since map should ordered on keys, chose implement based on java.util.treemap. following have implemented. has passed few test cases. questions :
are there existing data structures provide functionality?
if not, there way avoid iterations while performing
put? looks o(n^2), worst case.
class topscoremap { treemap<integer, string> map = new treemap<integer, string>(); int max = 0; public topscoremap() { this(5); } public topscoremap(int maxcapacity) { this.max = maxcapacity; } public void put(int score, string player) { if (map.size() < max) { map.put(score, player); } else { iterator<integer> = map.keyset().iterator(); while (it.hasnext()) { int currentkey = it.next(); if (currentkey < score) { map.remove(currentkey); map.put(score, player); return; } } } } }
you might want take @ priorityqueue, way don't need iterator...but should drop elements end if grows on limit
or maybe should use sortedmap:
public class t1 { sortedmap<integer, string> m=new treemap<integer, string>(); void add(integer i,string n){ m.put(i,n); if(m.size()>3){ m.tailmap(m.lastkey()).clear(); } system.out.println(m); } public static void main(string[] args) { t1 t = new t1(); t.add(1,"a");t.add(2,"b");t.add(3,"c");t.add(4,"d");t.add(0,"e"); } }
Comments
Post a Comment