每日一题：Leetcode面试题51.数组中的逆序对

矫情吗；* 2023-07-17 09:54 1阅读 0赞

## 题目描述： ##

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

**示例 1:**

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

**限制：**  
`0 <= 数组长度 <= 50000`

## 题解： ##

**题目难度**：困难

**解题思路**：

终于准备搞一搞Leetcode里的Hard题了。

本题是一道归并排序的典型题。题目理解起来十分容易，但想要在面试的时候解出最优算法还是需要付出一番苦功。

首先相信大家都能想出暴力法的思路，也就是对数组里的每一个数，都对数组中的其他数遍历一遍来判断是否能够构成逆序对，并统计逆序对的个数（也就是把数组中所有的两两组合都列举出来）。这样的算法时间复杂度已经到达了`O(n)=n^2`,想必面试官是不会满意的。

/* * 方法一：暴力法 时间复杂度O(n):n^2 **/
    func reversePairs(nums []int) int { 
    	res := 0
    	for i := 0 ;i < len(nums) ; i ++ { 
    		for j := i ; j <len(nums) ;j ++ { 
    			if nums[i] > nums[j] { 
    				res ++
    			}
    		}
    	}
    	return res
    }

从提交的结果来看，一道Hard级别的题目也不会轻而易举地让咱们通过，才第37个用例就TLE了。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70]  
那么我们咋办呢？接下来咱们就正式介绍一下这道题的正确思路——归并排序法。

首先，什么是归并排序呢？

> 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

我相信没个例子大家绝壁看不懂上边在说啥，咱们还是得通过几张图来了解一下归并排序的过程（本来想自己作个图，但是[图解排序算法][Link 1]的图已经珠玉在前了，这里引用。）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70 1][]  
也就是说，归并排序主要分为“分”和“治”两个过程。我们先把数组递归分为若干个小数组，并将每两个数组排序完，再**有序归并**到一起，如此递归。而如何实现把**两个有序的小数组**合并成**一个有序的大数组**，则是归并排序的核心。我们以上图中的最后一次合并为例，即\[4,5,7,8\]和\[1,2,3,6\]两个已经有序的子序列，合并为最终序列\[1,2,3,4,5,6,7,8\]。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70 2]  
具体合并过程如下。

func merge(nums []int, left, mid, right int) []int{ 
    	temp := []int{ } // 开辟临时数组用于存储新的合并完成后的数组
    	i := left // 左序列指针
    	j := mid+1 // 右序列指针
    	t := 0 // 临时数组指针
    	for i <= mid && j <= right { 
    		if nums[i] <= nums[j] { 
    			temp = append(temp, nums[i])
    			i++
    		} else { 
    			temp = append(temp, nums[j])
    			j++
    		}
    	}
    	for i <= mid { 
    		temp = append(temp, nums[i]) // 将左边剩余元素填充进temp中
    		i++
    	}
    	for j <= right { 
    		temp = append(temp, nums[j]) // 将右序列剩余元素填充进temp中
    		j++
    	}
    	return temp
    }

对于这道题而言，我们要做的就是在上面的合并过程中统计逆序数。  
️  
思路的核心点：

*  1.把数组拆分成两个元素为一组的数组，作为最底层。
 *  2.归并排序可以完成两个工作：1.计算最底层每个数组的逆序数，2.排序每个数组。
 *  3.归并倒数第二层，再进行排序和逆序数计算（res）。此时注意一点：相邻两个数交换顺序，不影响这两个数以外元素的逆序数计算。
 *  4.统计倒数第二层的逆序数方法的关键在于：  
    归并的两个数组都是有序依次排列的，所以在执行归并的时候就会发现，若右边数组第r个元素（right\[r\]）大于左边数组第l个元素（left\[l\]），则右边数组的这个元素一定大于左边数组从第i个一直到最后一个元素。这样的话，第j元素对应的逆序数就是len（left）-1。
 *  5.所以知道以上原理后，在每一层归并的过程中，我们只需要计算右边数组的元素相对于左边数组的逆序数就可以了，因为左边数组和右边数组本身的逆序数在递归的上一层就是已经统计好，无需再关心了。

所以总的来说就是在归并排序的基础上加上了一行`res +=mid-p1+1`的代码，实现了逆序数的统计工作。

**AC代码**：

/* * 方法二: 归并排序法 时间复杂度O(n)：nlog(n) **/
    func reversePairs(nums []int) int { 
    	if nums == nil || len(nums) < 2 { 
    		return 0 // 如果数组长度为0或1，那么直接返回0即可。
    	}
    	return process(nums, 0, len(nums)-1)
    }
    
    func process(nums []int, left, right int)int { 
    	if left == right { 
    		return 0
    	}
    	mid := left + (right-left)/2
    	return process(nums, left, mid)+process(nums, mid+1, right)+merge(nums, left, mid, right)
    }
    
    func merge(nums []int, left, mid, right int) int{ 
    	temp := []int{ } // 开辟临时数组用于存储新的合并完成后的数组
    	i := left // 左序列指针
    	j := mid+1 // 右序列指针
    	res := 0 // 用res记录逆序对的个数
    	t := 0 // 临时数组指针
    	for i <= mid && j <= right { 
    		if nums[i] <= nums[j] { 
    			temp = append(temp, nums[i])
    			i++
    		} else { 
    			res +=mid-p1+1 // 在归并的过程中记录逆序对个数
    			temp = append(temp, nums[j])
    			j++
    		}
    	}
    	for i <= mid { 
    		temp = append(temp, nums[i]) // 将左边剩余元素填充进temp中
    		i++
    	}
    	for j <= right { 
    		temp = append(temp, nums[j]) // 将右序列剩余元素填充进temp中
    		j++
    	}
    	return res // 返回本数组合并存在的逆序对个数
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70]: /images/20230528/f930e219bbf5447e8ce4145dfca287e3.png
[Link 1]: https://www.cnblogs.com/chengxiao/p/6194356.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70 1]: /images/20230528/3d484859718c42bdb95d16c6d914b760.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70 2]: /images/20230528/fff1aa2b4f2140f5a9f686a05bfcd3e5.png