493. 翻转对

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。 示例 1: 输入: [1,3,2,3,1] 输出: 2

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

注意:

  1. 给定数组的长度不会超过50000。
  2. 输入数组中的所有数字都在32位整数的表示范围内。

解题思路

归并排序

  1. class Solution {
  2. public:
  3.     int reversePairs(vector<int>& nums) {
  4.         return mergeAndCnt(nums,0,nums.size() - 1);
  5.     }
  7.     int mergeAndCnt(vector<int>& nums,int left,int right) {
  8.         if( left >= right) 
  9.             return 0;
  11.         int mid = left + ((right - left) >> 1);
  12.         int cnt = mergeAndCnt(nums,left,mid) + mergeAndCnt(nums,mid+1,right);
  13.         int j = mid + 1;
  14.         for(int i=left;i <= mid;i++) {
  15.             while( j <= right && nums[i] > nums[j]*2LL)
  16.                 j++;
  17.             cnt += j - (mid + 1);
  18.         }
  19.         merge(nums,left,mid,right);
  20.         return cnt;
  21.     }
  23.     void merge(vector<int>& nums,int left,int mid,int right) {
  24.         int n1 = mid - left + 1;
  25.         int n2 = right - mid;
  26.         int leftNums[n1],rightNums[n2];
  27.         for(int i=0;i< n1;i++)
  28.             leftNums[i] = nums[left + i];
  29.         for(int i=0;i< n2;i++)
  30.             rightNums[i] = nums[mid + 1 + i];
  31.         int i = 0,j = 0;
  32.         for(int k = left;k <= right;k++) {
  33.             if(j >= n2 || (i < n1 && leftNums[i] <= rightNums[j]))
  34.                 nums[k] = leftNums[i++];
  35.             else
  36.                 nums[k] = rightNums[j++];
  37.         }
  38.     }
  39. };