40ms C++ bitwise BST solution


  • 1
    L
    class Solution {
        class BSTNode {
        public:
            int cnt;
            BSTNode *lch, *rch;
            BSTNode():cnt(0), lch(NULL), rch(NULL){}
            ~BSTNode(){
                if (!lch) delete lch;
                if (!rch) delete rch;
            }
        } *root;
        
        int InsertAndCount(int val) {
            BSTNode *p = (val >= 0) ? root->rch : root->lch;
            int ret = (val >= 0) ? root->lch->cnt : 0;
            p->cnt++; 
            for (int i = 8 * sizeof(int) - 2; i >= 0; i--) {
                if ((val & (1 << i)) == 0) {
                    if (p->lch == NULL)
                        p->lch = new BSTNode();
                    p = p->lch;
                } else {
                    if (p->lch != NULL)
                        ret += p->lch->cnt;
                    if (p->rch == NULL)
                        p->rch = new BSTNode();
                    p = p->rch;
                }
                p->cnt++;
            }
            return ret;
        }
        
    public:
        Solution():root(new BSTNode()){
            root->lch = new BSTNode();   // negative
            root->rch = new BSTNode();   // positive
        }
        ~Solution(){
            delete root;
        }
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> ret(nums.size(), 0);
            for (int i = nums.size() - 1; i >= 0; i--)
                ret[i] = InsertAndCount(nums[i]);
            return ret;
        }
    };
    

Log in to reply
 

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