Accepted solution without using heaps (Binary search)


  • 0
    M
    class MedianFinder {
    List<Integer> list;
    
    public MedianFinder(){
        list = new ArrayList<Integer>();    
    }
    
    // Adds a number into the data structure.
    public void addNum(int num) {
        if(list.isEmpty()){
            list.add(num);
            return;
        }
        int index = findPlace(num,0,list.size()-1);
        list.add(index,num);
    }
    
    // Returns the median of current data stream
    public double findMedian() {
        int mid = list.size() /2;
        if(list.size() %2 == 0){
            int num1 = list.get(mid);
            int num2 = list.get(mid - 1);
            return (double)(num1 + num2)/2.0;
        }else{
            return (double)list.get(mid);
        }
    }
    
    int findPlace(int num, int beg, int end){
        int mid = (beg + end)/2;
        Integer midValue = list.get(mid);
        if(num == midValue) return mid;
        if(num < midValue){
            Integer left = (mid == 0)? new Integer(Integer.MIN_VALUE): list.get(mid-1);
            if(num >= left) return mid;
            return findPlace(num,beg,mid-1);
        }else{
            Integer right = (mid == list.size() -1)? new Integer(Integer.MAX_VALUE): list.get(mid+1);
            if(num <= right) return mid+1;
            return findPlace(num,mid+1,end);
        }
    }
    

    };

    // Your MedianFinder object will be instantiated and called as such:
    // MedianFinder mf = new MedianFinder();
    // mf.addNum(1);
    // mf.findMedian();


  • 0
    W

    I tried doing almost exactly the same thing in Python, but it took too long to run. Is that just because Python is slower or did I probably make a mistake somewhere? I don't know much about CS so pardon me if this is a stupid question.


  • 0
    M

    So our solution is theoretically slower than the optimal solution, since inserting at i th position in a linear data structure like Linked lists, Array Lists (dynamic arrays), arrays etc takes linear time i.e. o(n). While, heaps are faster with such operations. Thus, I'd recommend learning the optimal solution (it's very interesting). I can help you with understanding that if you'd like.

    So why this solution and how did this get accepted?
    This is just another way of doing the problem, I posted this merely because it is interesting. This got accepted because I believe Java has a pretty good implementation of ArrayLists and the test cases mustn't have been too stringent.

    Why didn't your solution get accepted?
    Some Python run-times can be slower than Java. http://stackoverflow.com/questions/672857/is-python-slower-than-java-c

    I'm not a Python developer so can't speak much on that.
    Other than that, there could very well be some problem with the implementation.

    Side note: Stupid questions make smart people ;)


Log in to reply
 

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