C++ 128ms beats 99% using BST and Double Link List


  • 2
    K
    class MedianFinder {
    private:
        struct TreeNode {
            int val;
            TreeNode *left;
            TreeNode *right;
            TreeNode *prev;
            TreeNode *next;
    
            TreeNode(int x) : val(x), left(NULL), right(NULL), next(NULL), prev(NULL) {}
    
            void Add(TreeNode *node) {
                if (node->val < val) {
                    if (left) {
                        left->Add(node);
    
                    } else {
                        left = node;
                        node->next = this;
                        node->prev = prev;
                        if (prev) {
                            prev->next = node;
                        }
    
                        prev = node;
                    }
    
                } else {
                    if (right) {
                        right->Add(node);
    
                    } else {
                        right = node;
                        node->prev = this;
                        node->next = next;
                        if (next) {
                            next->prev = node;
                        }
    
                        next = node;
                    }
                }
            }
        };
    
        size_t count;
        TreeNode *root;
        TreeNode *med;
    
    public:
        MedianFinder() : root(NULL) {}
    
        // Adds a number into the data structure.
        void addNum(int num) {
            TreeNode *node = new TreeNode(num);
            if (root == NULL) {
                root = med = node;
                count = 1;
    
            } else {
                root->Add(node);
                count++;
                if (count & 1) {
                    if (num >= med->val) {
                        med = med->next;
                    }
    
                } else {
                    if (num < med->val) {
                        med = med->prev;
                    }
                }
            }
        }
    
        // Returns the median of current data stream
        double findMedian() {
            if (count & 1) {
                return med->val;
            } else {
    
                return (med->val + med->next->val) / 2.0;
            }
        }
    };

  • 0
    A

    Very short and easy to understand c++ solution using vector :

    vector<int>v;
    void addNum(int num) {
        if(v.size()==0)
        {
            v.push_back(num);
        }
        else
        {
            vector<int>::iterator it;
            it=lower_bound(v.begin(),v.end(),num);
            v.insert(it,num);
        }
    }
    double findMedian() {
        int n=v.size();
        if(n&1)
        {
            return (double)(v[n/2]);
        }
        else
        {
            return ((double)(v[n/2-1])+(double)(v[n/2]))/2.0;
        }
    }
    

Log in to reply
 

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