分治-归并排序_代码007(未授权)

在这里插入图片描述

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

输入：nums = [-1]
输出：[0]

示例 3：

输入：nums = [-1,-1]
输出：[0,0]

提示：

nums: [15,17,20,23,12,3]
index:[ 0, 1, 2, 3, 4,5]

class Solution {
    vector&lt;int&gt; ret;
    vector&lt;int> index;
    int tmpNums[500001];
    int tmpIndex[500001];
public:
    vector<int> countSmaller(vector<int>&amp; nums)
    {
        int n = nums.size();
        ret.resize(n);
        index.resize(n);
        for(int i=0; i<n; i++)  index[i] = i;
        mergeSort(nums, 0, n-1);
        return ret;
    }

    void mergeSort(vector<int>&amp; nums, int left, int right)
    {
        if(left >= right)   return;
        int mid = (left + right) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);

        int cur1 = left,
            cur2 = mid+1,
            i = 0;
        while(cur1 <= mid &amp;&amp; cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];    
            }
            else
            {
                ret[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }
        while(cur1 <= mid)
        {
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while(cur2 <= right)
        {
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        for(int i=left; i<=right; i++)
        {
            nums[i] = tmpNums[i-left];
            index[i] = tmpIndex[i-left];
        }
    }
};

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

输入: [1,3,2,3,1]
输出: 2

输入: [2,4,3,5,1]
输出: 3

class Solution {
    int tmp[50001];
public:
    int reversePairs(vector<int>&amp; nums)
    {
        int n = nums.size();
        return mergeSort(nums,0,n-1);
    }

    int mergeSort(vector<int>&amp; nums, int left, int right)
    {
        if(left >= right)   return 0;

        int ret = 0;
        int mid = (left+right)>>1;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid+1, right);

        int cur1 = left,
        cur2 = mid +1,
        i = left;
        while(cur2 <= right)
        {
            while(cur1 <= mid &amp;&amp; nums[cur2] >= nums[cur1]/2.0)   cur1++;
            if(cur1 > mid)  break;
            ret += mid - cur1 + 1;
            cur2++; 
        }
        //合并
        cur1 = left,
        cur2 = mid+1,
        i = left;
        while(cur1 <= mid &amp;&amp; cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2]?nums[cur1++]:nums[cur2++];            
        while(cur1 <= mid)  tmp[i++] = nums[cur1++];
        while(cur2 <= right)    tmp[i++] = nums[cur2++];

        for(int i=left; i<=right; i++)  nums[i] = tmp[i];
        return ret;
    }
};