JZOffer-51

剑指 Offer 51. 数组中的逆序对

1 题目描述

• 题目链接：剑指 Offer 51. 数组中的逆序对

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

示例1：

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

2 思路

  逆序对定义为原数组位于前边的元素大于后边的元素，那么这两个元素就是一个逆序对。那么刚好与归并排序相对应，归并排序是将数组按二分法逐步划分为小区间并对小区间进行排序，如果左边区间的当前元素大于右边区间的当前元素，那么由于当前左边区间和右边区间都已经是排完序了的，那么左边区间当前位置到区间末尾间的元素与右边区间当前元素构成了逆序对。也就是说，在归并排序中，当从右边区间取值放到左边区间时就更新逆序对数，完成归并排序后即求得原数组中的逆序对总数。

class Solution {
    int mergeSort(vector<int>& nums, vector<int>& tmp, int left, int right) {
        if(left >= right)   return 0;
        int mid = left + (right - left) / 2;
        // 分
        int ans = mergeSort(nums, tmp, left, mid) + mergeSort(nums, tmp, mid+1, right);
        // 治
        int i = left, j = mid + 1;
        for(int k = left; k <= right; ++k)
            tmp[k] =nums[k];
        for(int k = left; k <= right; ++k) {
            if(i==mid+1)
                nums[k] = tmp[j++];
            else if(j==right+1 || tmp[i]<=tmp[j])
                nums[k] = tmp[i++];
            else {
                nums[k] = tmp[j++];
                ans += mid - i + 1;
            }
        }
        return ans;
    }
public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp(n);
        return mergeSort(nums, tmp, 0, n-1);
    }
};