本文共 1464 字，大约阅读时间需要 4 分钟。

1. 题目

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

你需要返回给定数组中的重要翻转对的数量。

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

来源：力扣（LeetCode）

2. 归并排序求解

• 参考

class Solution {
       int count = 0;    int *temp;public:    int reversePairs(vector
   
    & nums) {
           temp = new int[nums.size()];        rp(nums,0,nums.size()-1);        return count;    }    void rp(vector
    
     & nums, int left, int right)     {
           if(left >= right)            return;        int mid = (left+right)/2;        rp(nums,left,mid);        rp(nums,mid+1,right);        merge(nums,left,mid,right);    }    void merge(vector
     
      & nums, int left, int mid, int right)    {
           int i = left, j = mid+1, k;        while(i <= mid && j <= right)        {
               if((long)nums[i] > 2*long(nums[j]))            {
                   count += mid-i+1;                j++;            }            else                i++;        }//先处理问题        //下面再排序        i = left, j = mid+1, k = left;        while(i <= mid && j <= right)        {
               if(nums[i] <= nums[j])                temp[k++] = nums[i++];            else                temp[k++] = nums[j++];        }        while(i <= mid)            temp[k++] = nums[i++];        while(j <= right)            temp[k++] = nums[j++];        for(i = left; i <= right; ++i)            nums[i] = temp[i];    }};
     
    
   

转载地址：https://michael.blog.csdn.net/article/details/101236925 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！