Java solution with binary search


  • -2
    G
    List<Integer> list = new ArrayList<Integer>();
    // Adds a number into the data structure.
    public void addNum(int num) {
    	int len = list.size();
    	
    	int low = 0 ; 
    	int high = len-1;
    	int mid;
    	while(low<=high){    		
    		mid = low + (high-low)/2;    		
    		int tempmid = list.get(mid);
    		if(num <= tempmid){
    			high = mid -1;
    		}else{
    			low = mid +1 ;
    		}
    	}    	
        list.add(low,num);
    }
    
    // Returns the median of current data stream
    public double findMedian() {
        int len = list.size();
    	if(len==0) return 0;
    	if(len%2==1) return list.get(len/2);
    	else return(list.get(len/2-1)+list.get(len/2))/2.0;        
    }

Log in to reply
 

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