C++ using treap/binary indexed tree


  • 1
    C

    using treap:

    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector <int> vec(0);
            root = NULL;
            for (auto it = nums.rbegin(); it != nums.rend(); it++) {
                root = insert(root, *it);
                vec.push_back(calcSmallerThanVal(root, *it));
            }
            
            reverse(vec.begin(), vec.end());
            return vec;
        }
        
    private:
        struct Node {
            int val, cnt, priority;
            Node *left, *right;
            
            Node (int val) {
                this->val = val;
                this->cnt = 1;
                this->priority = rand();
                this->left = NULL;
                this->right = NULL;
            }
        };
        
        typedef Node *Tree;
        
        Tree root;
        
        Tree insert(Tree root, int val) {
            if (root == NULL) return new Node(val);
            if (val <= root->val) {
                root->left = insert(root->left, val);
                if (root->left->priority > root->priority) {
                    root = rightRotate(root);
                }
            } else {
                root->right = insert(root->right, val);
                if (root->right->priority > root->priority) {
                    root = leftRotate(root);
                }
            }
            maintain(root);
            return root;
        }
        
        Tree leftRotate(Tree root) {
            Tree newRoot = root->right;
            root->right = newRoot->left;
            newRoot->left = root;
            
            maintain(newRoot->left);
            maintain(newRoot->right);
            maintain(newRoot);
            
            return newRoot;
        }
        
        Tree rightRotate(Tree root) {
            Tree newRoot = root->left;
            root->left = newRoot->right;
            newRoot->right = root;
            
            maintain(newRoot->left);
            maintain(newRoot->right);
            maintain(newRoot);
            
            return newRoot;
        }
        
        //calc smaller than val count
        int calcSmallerThanVal(Tree root, int val) {
            if (root == NULL) return 0;
            if (val <= root->val) {
                return calcSmallerThanVal(root->left, val);
            } else {
                return treeNumCount(root->left) + 1 + calcSmallerThanVal(root->right, val);
            }
        }
        
        int treeNumCount(Tree root) {
            if (root == NULL) return 0;
            return root->cnt;
        }
        
        void maintain(Tree root) {
            if (root == NULL) return;
            root->cnt = treeNumCount(root->left) + treeNumCount(root->right) + 1;
        }
    };
    

    using Binary Indexed Tree:

    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector <int> clone = nums;
            vector <int> ans;
            unordered_map <int, int> idx;
            sort(clone.begin(), clone.end());
            int cnt = 0;
            for (int i = 0; i < clone.size(); i++) {
                if (i == 0 || clone[i] != clone[i-1]) idx[clone[i]] = ++cnt;
            }
            v.resize(cnt+1);
            for (auto it = nums.rbegin(); it != nums.rend(); it++) {
                int val = idx[*it];
                ans.push_back(calc(val - 1, cnt));
                add(val, cnt);
            }
            
            reverse(ans.begin(), ans.end());
            return ans;
        }
        
    private:
        
        vector <int> v;
        
        void add(int val, int cnt) {
            while (val <= cnt) {
                v[val]++;
                val += (val - 1 ^ val) & val;
            }
        }
        
        int calc(int val, int cnt) {
            int sum = 0;
            while (val) {
                sum += v[val];
                val = val & (val - 1);
            }
            return sum;
        }
    };
    

  • 0
    D
    This post is deleted!

  • 0
    D
    This post is deleted!

Log in to reply
 

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