[easy to understand with details] C++ implementation inspired from the Binary Index Tree


  • 2

    My first implementation can't pass the case

    [11, 11]
    

    After analyzing all the code, I know that the problem lays at the code to compute the places[] array.

    when the numbers equal, I SHOULD set the number index different and the latter appearance should

    corresponds to bigger index. So My original code can not satisfy this condition.

    all the cases contain duplicate number 
    

    HOW SHOULD I CHANGE MY CODE TO DEAL WITH THIS CASE?

    Solution:

     result[i]=bit_sum(places[i]-1);
    

    calculate the sum to the places[i]-1 is the sum of the small numbers.

    class Solution {
        vector<int> bit;
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> result(nums.size(), 0);
            bit.resize(nums.size()+1, 0);
            
            //get the ordered-index-array
            vector<int> sorted_nums(nums);
            vector<int> places(nums.size(), 0);
            sort(sorted_nums.begin(), sorted_nums.end());
            for (int i = 0; i < nums.size(); ++i) {
                places[i] = lower_bound(sorted_nums.begin(), sorted_nums.end(), nums[i]) - sorted_nums.begin();
                cout<<i<<"th places:"<<places[i]<<endl;
            }
            
            for(int i=places.size()-1; i>=0; i--){
                result[i]=bit_sum(places[i]-1);
                bit_add(places[i], 1);
            }
            
            return result;
        }
        
        int bit_last(int i){
            return i&-i;
        }
        
        void bit_add(int i, int val){
            i++;
            while(i<bit.size()){
                bit[i]+=val;
                i=i+bit_last(i);
            }
        }
        
        int bit_sum(int i){
            i++;
            int sum=0;
            while(i>0){
                sum+=bit[i];
                i=i-bit_last(i);
            }
            return sum;
        }
    };
    
    
    /*
    5,2,6,1
    2,1,3,0
    from-end-to-start-traverse
    insert(0)
    get_sum(0)
    insert(3)
    get_sum(3)
    insert(1)
    get_sum(1)
    insert(2)
    get_sum(2)
    */

  • 2
    class Solution {
        vector<int> bit;
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> sorted_nums(nums);
            vector<int> dict(nums.size(), 0);
            vector<int> result(nums.size(), 0);
            bit.resize(nums.size()+1, 0);
            /*** use-O(N)-space-to-get-the-order-number-array ***/
            unordered_map<int, int> map;
            sort(sorted_nums.begin(), sorted_nums.end());
            for(int i=0; i<nums.size(); i++){
                map[sorted_nums[i]]=i+1;
            }
            for(int i=0; i<nums.size(); i++){
                dict[i]=map[nums[i]];
            }
            /*** use binary-index-tree-idea to query the result in O(NlogN) ***/
            for(int i=dict.size()-1; i>=0; i--){
                result[i]=bit_sum(dict[i]-1);
                bit_add(dict[i], 1);
            }
            return result;
        }
        
        int last_bit(int i){
            return i&-i;
        }
        
        void bit_add(int i, int val){
            i++;
            while(i<bit.size()){
                bit[i]+=val;
                i+=last_bit(i);
            }
        }
        
        int bit_sum(int i){
            i++;
            int sum=0;
            while(i>0){
                sum+=bit[i];
                i-=last_bit(i);
            }
            return sum;
        }
    };

  • 0
    2
    class Solution {
        vector<int> bit;
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> sorted_nums(nums);
            vector<int> dict(nums.size(), 0);
            vector<int> result(nums.size(), 0);
            bit.resize(nums.size() + 1, 0);
            
            unordered_map<int, int> map;
            sort(sorted_nums.begin(), sorted_nums.end());
            for(int i = 0; i < nums.size(); i++) {
                map[sorted_nums[i]] = i + 1;
            }
            for(int i = 0; i < nums.size(); i++) {
                dict[i] = map[nums[i]];
            }
            
            for(int i = dict.size()-1; i >= 0; i--) {
                result[i] = bit_sum(dict[i] - 1);
                bit_add(dict[i], 1);
            }
            
            return result;
        }
        
        int last_bit(int i) {
            return i & (-i);
        }
        
        void bit_add(int i, int val) {
            i++;
            while(i < bit.size()) {
                bit[i] += val;
                i += last_bit(i);
            }
        }
        
        int bit_sum(int i) {
            i++;
            int sum = 0;
            while(i > 0) {
                sum += bit[i];
                i -= last_bit(i);
            }
            return sum;
        }
    };

  • 1
    F
    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> t, res(nums.size());
            for (int i = nums.size() - 1; i >= 0; --i) {
                int d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i]));
                res[i] = d;
                t.insert(t.begin() + d, nums[i]);
            }
            return res;
        }
    };

  • 0
    T

    @fight.for.dream
    use map instead of vector<int> could be more efficient because insert in map is o(log(n)) while in vector it is o(n)


Log in to reply
 

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