剑指Offer - 面试题51. 数组中的逆序对（归并排序，求逆序对）

Shela ·

更新时间:2024-11-10

· 657 次阅读

1. 题目

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

示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 归并排序

详见 LeetCode 315. 计算右侧小于当前元素的个数（二叉查找树&二分查找&归并排序逆序数总结）

方法1：后半部出队写入临时数组时，sum + 前半部没有出来的个数(比后部出队的那个大)

方法2：前半部出队，sum+ 后半部已经出队的数量(比出队的那个小)，有后续操作，当后半部全部出队了完毕，前半部继续出队，整个后半部分都比剩余的前半部分小。

两种方法只能取其一。

class Solution {
	int sum = 0;
	vector temp;
public:
    int reversePairs(vector& nums) {
        temp.resize(nums.size());
    	mergesort(nums,0,nums.size()-1);
    	return sum;
    }
    void mergesort(vector& arr, int l ,int r)
    {
    	if(l >= r)
    		return;
    	int mid = l + ((r-l)>>1);
    	mergesort(arr,l,mid);
    	mergesort(arr,mid+1,r);
    	merge(arr,l,mid,r);
    }
    void merge(vector& arr, int l, int mid, int r)
    {
    	int i = l, j = mid+1, k = 0;
    	// 方法1：后半部出队，sum+前半部 没有出来的个数(比后面大的)
    	while(i <= mid && j <= r)
    	{
    		if(arr[i] <= arr[j])
    			temp[k++] = arr[i++];
    		else
    		{
    			temp[k++] = arr[j++];
    			sum += mid-i+1;
    		}
    	}
    	while(i <= mid)//后面都出完了，前半部还剩一些
    		temp[k++] = arr[i++];
    	while(j <= r)
    		temp[k++] = arr[j++];
    	for(i = l,j = 0; j < k; )
    		arr[i++] = temp[j++];
		//---------------------------------------------------
    	//方法2：前半部出队，sum+ 后半部 已经出队的数量(比前面的小)
    	while(i <= mid && j <= r)
    	{
    		if(arr[i] <= arr[j])
    		{
    			temp[k++] = arr[i++];
    			sum += j-(mid+1);
    		}
    		else
    			temp[k++] = arr[j++];
    	}
    	while(i <= mid)//后面都出完了，前半部还剩一些，还需要操作
    	{
    		temp[k++] = arr[i++];
    		sum += j-(mid+1);
    	}
    	while(j <= r)
    		temp[k++] = arr[j++];
    	for(i = l, j = 0; j < k; )
    		arr[i++] = temp[j++];
    }
};

在这里插入图片描述