Simple BST solution


  • 1
    Z

    ##BST solution

    public class MedianFinder {
        private Tree tree ;
        /** initialize your data structure here. */
        public MedianFinder() {
            tree = new Tree();
        }
        
        public void addNum(int num) {
            tree.add(num);
        }
        
        public double findMedian() {
            int size = tree.size();
            int half = size >> 1;
            if(size %2 == 1){
                return tree.getIth(1 + half);
            }
            else{
                return (tree.getIth(half) + tree.getIth(half +1)) / (double)2;
            }
        }
    }
    
        // BST
    class Tree{
        private static class Node {
            int cnt;
            int value;
            Node left; 
            Node right;
            
            Node(int v){value = v; cnt = 1;}
        }
        
        private Node root ;
        
        void add(int n){
            if(root == null){
                root = new Node(n);
                return ;
            }
            
            // root not null. 
            Node cur = root;
            
            while(true){
                cur.cnt ++; // important
                if(n < cur.value){
                    if(cur.left == null){
                        cur.left = new Node(n);
                        break;
                    }
                    cur = cur.left;
                    
                }
                else{
                    if(cur.right == null){
                        cur.right = new Node(n);
                        break;
                    }
                    cur = cur.right;
                }
            }
        }
        
        // get ith largest element, i is 1-based.
        int getIth(int i){
            if(i <= 0 || i > size()) throw new RuntimeException("wrong args: " + i);
            
            Node cur = root;
            while(true){
                int leftCnt = cur.left == null ? 0: cur.left.cnt;
                int rightCnt = cur.right  == null ? 0: cur.right.cnt;
                
                if(leftCnt + 1 == i) // root.
                    return cur.value;
                else if(leftCnt >= i){
                    cur = cur.left;
                }
                else{
                    cur = cur.right;
                    i -= (1 + leftCnt);
                }
            }
        }
        
        int size(){
            return root == null ? 0: root.cnt;
        }
    }

Log in to reply
 

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