C++ solution with Fenwick tree


  • -1
    S
     int BiSearch(const vector<int>& n,const int& target,const int len){
            int l = 0, r = len-1;
            while(l < r){
                int mid = l + ((r - l)>>1);
                if(n[mid] == target) return mid;
                else if(n[mid] < target)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
        }
    
    int lowBit(int x){  // calculate 2^k
        return x & (-x);
    }
    
    void add(vector<int>& s, int val, int i){
        for(; i < s.size(); i += lowBit(i))  
            s[i] += 1;
    }
    
    int query(vector<int>& s, int i) {
        int ans = 0;
        for(; i > 0; i -= lowBit(i))
            ans += s[i];
        return ans;
    }
    
    vector<int> countSmaller(vector<int>& nums) {
        const int len = nums.size();
        vector<int> clone(nums);
        vector<int> s(len,0);
        vector<int> ans(len,0);
        for(int i = 0; i < len; i++)   clone[i] = nums[i];  
        sort(clone.begin(),clone.end());
        for(int i = 0; i < len; i++)   nums[i] = BiSearch(clone,nums[i],len);  //discretization
        
        
        for(int i = len-1; i >= 0; i--){
            ans[i] = query(s,nums[i]);
            add(s,1,nums[i]+1);
        }
        return ans;
    }

  • 1
    P

    typo: in add, you want to add val instead of 1? The only value you add is 1 anyway.


Log in to reply
 

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