面试题51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]

输出: 5

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：BF法（超时）

  1. class Solution {
  2. public:
  3.     int reversePairs(vector<int>& nums) {
  4.         int size = nums.size();
  5.         if(size <= 1)
  6.             return 0;
  8.         int ret = 0;
  10.         for(int i = 0; i < size; i++)
  11.         {
  12.             int tmp = nums[i];
  13.             for(int j = i + 1; j < size; j++)
  14.             {
  15.                 if(tmp > nums[j])
  16.                     ret++;
  17.             }
  18.         }
  20.         return ret;
  21.     }
  22. };

方法二：后退法（超时）

  1. class Solution {
  2. public:
  3.     int reversePairs(vector<int>& nums) {
  4.         int size = nums.size();
  5.         if(size <= 1)
  6.             return 0;
  8.         int ret = 0;
  10.         map<int, int>store;
  11.         for(int i = size - 1; i >= 0; i--)
  12.         {
  13.             int tmp = nums[i];
  14.             store[tmp]++;
  16.             for(auto &index : store)
  17.             {
  18.                 if(index.first == tmp)
  19.                     break;
  20.                 else
  21.                     ret += index.second;
  22.             }
  23.         }
  25.         return ret;
  26.     }
  27. };

方法三：归并排序

  1. class Solution {
  2. public:
  3.     int mergeSort(vector<int>& nums, vector<int>& tmp, int l, int r)
  4.     {
  5.         if(l >= r)
  6.             return 0;
  8.         int mid = (l + r) / 2;
  9.         int inv_count = mergeSort(nums, tmp, 1, mid) + mergeSort(nums, tmp, mid+1, r);
  11.         //合并数组时计算逆序对个数
  12.         int i = 1, j = mid + 1, pos = 1;
  13.         while(i <= mid && j <= r){
  14.             if(nums[i] <= nums[i]) {
  15.                 tmp[pos] = nums[i];
  16.                 ++i;
  17.                 inv_count += (j - (mid + 1));
  18.             }
  19.             else {
  20.                 tmp[pos] = nums[j];
  21.                 ++j;
  22.             }
  23.             ++pos;
  24.         }
  26.         for(int k = i; k <= mid; ++k)
  27.         {
  28.             tmp[pos++] = nums[k];
  29.             inv_count += (j - (mid + 1));
  30.         }
  31.     }
  32. }
  1. public class Solution {
  3.     public int reversePairs(int[] nums) {
  4.         int len = nums.length;
  6.         if (len < 2) {
  7.             return 0;
  8.         }
  10.         int[] copy = new int[len];
  11.         for (int i = 0; i < len; i++) {
  12.             copy[i] = nums[i];
  13.         }
  15.         int[] temp = new int[len];
  16.         return reversePairs(copy, 0, len - 1, temp);
  17.     }
  19.     /**
  20.      * nums[left..right] 计算逆序对个数并且排序
  21.      *
  22.      * @param nums
  23.      * @param left
  24.      * @param right
  25.      * @param temp
  26.      * @return
  27.      */
  28.     private int reversePairs(int[] nums, int left, int right, int[] temp) {
  29.         if (left == right) {
  30.             return 0;
  31.         }
  33.         int mid = left + (right - left) / 2;
  34.         int leftPairs = reversePairs(nums, left, mid, temp);
  35.         int rightPairs = reversePairs(nums, mid + 1, right, temp);
  37.         if (nums[mid] <= nums[mid + 1]) {
  38.             return leftPairs + rightPairs;
  39.         }
  41.         int crossPairs = mergeAndCount(nums, left, mid, right, temp);
  42.         return leftPairs + rightPairs + crossPairs;
  43.     }
  45.     /**
  46.      * nums[left..mid] 有序，nums[mid + 1..right] 有序
  47.      *
  48.      * @param nums
  49.      * @param left
  50.      * @param mid
  51.      * @param right
  52.      * @param temp
  53.      * @return
  54.      */
  55.     private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
  56.         for (int i = left; i <= right; i++) {
  57.             temp[i] = nums[i];
  58.         }
  60.         int i = left;
  61.         int j = mid + 1;
  63.         int count = 0;
  64.         for (int k = left; k <= right; k++) {
  66.             if (i == mid + 1) {
  67.                 nums[k] = temp[j];
  68.                 j++;
  69.             } else if (j == right + 1) {
  70.                 nums[k] = temp[i];
  71.                 i++;
  72.             } else if (temp[i] <= temp[j]) {
  73.                 nums[k] = temp[i];
  74.                 i++;
  75.             } else {
  76.                 nums[k] = temp[j];
  77.                 j++;
  78.                 count += (mid - i + 1);
  79.             }
  80.         }
  81.         return count;
  82.     }
  83. }

时间复杂度：同归并排序O（nlogn）
空间复杂度：同归并排序O（n），因为归并排序需要用到一个临时数组