BIT solution runs O(nlogn ) time complexity and O(n) space complexity


  • 0
    Y
    class Solution {
    public:
        int* tree;
        void ins(int t,int n)
        {
            while(t<=n)
            {
                tree[t]++;
                t+=(-t)&t;
            }
        }
        int query(int t)
        {
            int ret=0;
            while(t>0)
            {
                ret+=tree[t];
                t-=(-t)&t;
            }
            return ret;
        }
        
        vector<int> countSmaller(vector<int>& nums) {
            vector<int>dcre(nums);
            int n=nums.size();
            vector<int>ans(n);
            
            int i,j;
            //dcre.assign(nums.begin(),nums.end());
            sort(dcre.begin(),dcre.end());
            int c=unique(dcre.begin(),dcre.end())-dcre.begin();
            //dcre.erase(dcre.begin()+c,dcre.end());
            tree=new int[c+5];
            memset(tree,0,sizeof(int)*(c+5));
            for(i=n-1;i>=0;i--)
            {
                j=lower_bound(dcre.begin(),dcre.begin()+c,nums[i])-dcre.begin()+1;
                ans[i]=query(j-1);
                ins(j,c);
            }
            return ans;
        }
    };

Log in to reply
 

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