C++ net merge sort solution


  • 3
    C
    class Solution {
    public:
        vector<int> ans;
        void merge_s(vector<pair<int, int> > &v, int left, int right) {
            if (left + 1 >= right)
                return;
            vector<pair<int, int> > tmp;
            int mid = (left + right) / 2;
            merge_s(v, left, mid);
            merge_s(v, mid, right);
            int li = left, ri = mid;
            while (li < mid || ri < right) {
    
                while (ri < right && (li >= mid || (v[ri].first < v[li].first))) {
                    tmp.push_back(v[ri++]);
                }
    
                while (li < mid && (ri >= right || (v[li].first <= v[ri].first))) {
                    tmp.push_back(v[li]);
                    ans[v[li].second] += ri - mid;
                    li++;
                }
    
            }
            for (int i = left;i < right;i++)
                v[i] = tmp[i - left];
        }
        vector<int> countSmaller(vector<int>& nums) {
            vector<pair<int, int> > v;
            ans.resize(nums.size(), 0);
            for (int i = 0;i < nums.size();i++)
                v.emplace_back(nums[i], i);
            merge_s(v, 0, nums.size());
            return ans;
        }
    };

Log in to reply
 

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