Binary indexed tree, C++, 45 lines, 50 ms


  • 0
    I
    struct comp {
    	bool operator() (const pair<int, int>& val1, const pair<int, int>& val2) {
    		return val1.first<val2.first;
    	}
    } mycomp;
    
    class Solution {
    public:
    	int lowbit(int idx)
    	{
    		return idx&(-idx);
    	}
    
    	vector<int> countSmaller(vector<int>& nums) {
    		vector<pair<int, int> > sorted_list;
    		vector<pair<int, int> > BIT_list;
    		vector<int> counts;
    		int len = nums.size();
    		if (len == 0)
    			return counts;
    
    		sorted_list.resize(len);
    		BIT_list.resize(len);
    		counts.resize(len);
    
    		for (int i = 0; i<len; ++i)
    			sorted_list[i] = make_pair(nums[i], i);
    		stable_sort(sorted_list.begin(), sorted_list.end(), mycomp);  // pay attention to equivalent elements, must keep in the same order
    		
    		for (int i = 0; i<len; ++i)
    			BIT_list[sorted_list[i].second] = make_pair(i, 0);
    
    		for (int i = 0; i<len; ++i)
    		{
    			counts[i] += BIT_list[i].first;
    			for (int j = BIT_list[i].first; j<len; j += lowbit(j + 1))
    				counts[i] += BIT_list[j].second;
    			for (int j = BIT_list[i].first; j >= 0; j -= lowbit(j + 1))
    				++BIT_list[j].second;
    			for (int j = len - 1; j >= 0; j -= lowbit(j + 1))
    				--BIT_list[j].second;
    		}
    		return counts;
    	}
    };

Log in to reply
 

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