Java Solution with binary search tree


  • 3
    L
    public class AssignCookies {
        public static int findContentChildren(int[] g, int[] s) {
        	int count = 0;
        	TreeMap<Integer,Integer> tree = new TreeMap<>();
        	for(int temp : s){
        		Integer num = tree.get(temp);
        		num = num==null?0:num;
        		tree.put(temp,num+1);
        	}
        	for(int temp : g){
        		Integer targ = tree.ceilingKey(temp);
        		if(targ!=null){
        			Integer num = tree.get(targ);
        			if(num>0){
        				count++;
        				if(num==1){
        					tree.remove(targ);
        				}else{
                                            tree.put(targ, num - 1);
                                    }
        			}
        		}
        	}
            return count;
        }
    }
    

  • 0
    A

    @Lisl Great solution. But I don't think this is binary search.


  • 0
    L

    @aswin2 Because TreeMap in Java is realization of red-black tree,we can think it is a binary search


  • 0
    A

    @Lisl Ah! Thank you


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.