剑指 Offer . 数组中的逆序对

2023/3/22美团面试

题目

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

示例2：
输入：[1，2，3，4，5，6，7，0]
输出：7

时间复杂度要求控制在O(n logn),所以不能用两个for循环进行比较。
最简单的方法——归并。
归并排序我之前只是搞懂了原理没有怎么去实现，搞得我遇到这道题直接抓瞎了，MD气死我了！
请同学们一定要多写代码。好记性不如烂笔头。

排序部分

int mergeSort(vector<int>& nums, int left, int right, vector<int>& tmp)
    {
  
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid, tmp) + mergeSort(nums, mid + 1, right, tmp);//mid+1-right;//left-mid
        int i = left, j = mid + 1, k = left;

        for (k = left; k <= right; k++)//至关重要，要更新tmp
        {
  
            tmp[k] = nums[k];
        }
        for (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++];
                count += (mid - i + 1);
            }
        }
        return count;
    }

有的人喜欢搞两个函数，我觉得太麻烦了，这样子搞我更加直观。
原理图如下：

其实就是不断地二分，二分之后再二分知道编程一个元素一组，一个元素一组肯定是有序的呀，然后再两个两个比较，这里的两个两个是前后跨度为2的（如图所示），然后再四个四个比较（我就按双数来了，有可能是3，4个比较；4，5个比较，都可以，重在好理解！）然后再8，8个比较直到这个变成一个大组，这个大组都是有序的啦！

class Solution {
  
public:

    //2023/3/22美团面试

    int mergeSort(vector<int>& nums, int left, int right, vector<int>& tmp)
    {
  
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid, tmp) + mergeSort(nums, mid + 1, right, tmp);//mid+1-right;//left-mid
        int i = left, j = mid + 1, k = left;

        for (k = left; k <= right; k++)//至关重要，要更新tmp
        {
  
            tmp[k] = nums[k];
        }
        for (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++];
                count += (mid - i + 1);
            }
        }
        return count;
    }
    int reversePairs(vector<int>& nums)
    {
  
        if (nums.size() < 2) return 0;
        vector<int> tmp(nums.size());
        
        int c=mergeSort(nums, 0, nums.size() - 1, tmp);
        
        return c;
    }
};

int main()
{
  
    Solution A;
    vector<int> nums = {
   7,5,6,4 };
    cout << A.reversePairs(nums) << endl;
    for (auto i : nums)
    {
  
        cout << i << ' ';
    }
    cout << endl;
    
    return 0;
}