【分治】数组中的逆序对

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

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

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

---

解题思路：归并排序 + 细节处理

思路一：寻找比该值之前大的元素个数

​ 这道题如果是暴力破解的话比较简单，就是枚举所有的情况即可，但是时间复杂度肯定不过关，毕竟这是一道困难题，所以我们要想想其它方法，但其实这个思路不容易想到，所以这里直接说了，当作一种解题思路的经验，也就是使用归并排序来处理！

​ 首先，因为归并排序就是一个分治的思想，那么就可以把一个区间分为左右区间来单独处理，并且 归并排序是一个后序遍历，也就是说，当我们把一个区间分为左右区间去各自递归之后，当处理完毕回来的时候，此时左右区间是各自有序的了，如下图所示：

​ 接着我们就想，既然左右区间都有序了，那么在合并两个有序区间的时候，是不是能够顺便处理逆序对的情况，答案是可以的，下面我们就来讨论一下！

​ 下面我们单独拎出这两个处理完的，排完序的左右区间出来（递归思想，只要我们理解了一层，那么下一层的处理也是同样的，所以我们只需要考虑一层的情况即可），标记一些边界变量，如下图所示：

​ （注意，上面的两个区间看起来是分开的，但实际上它们仍然还是存在同一个数组 nums 中，这里只是为了看起来生动一点！）

​ 此时在合并这两个区间的时候，会根据 nums[cur1] 和 nums[cur2] 的大小来选取对应的值逐步填到合并数组中，此时我们就想，既然我们要求的是比当前元素都大的元素的个数，那我们就根据它们的大小来分别讨论一下会有什么情况（下面讨论的是升序的情况）：

• 如果 nums[cur1] <= nums[cur2] 的话：

  • 此时没有什么特殊情况，因为没办法找出左右区间之间有什么关系能很好的快速处理逆序对，所以直接 将 nums[cur1] 拷贝到临时数组中，然后让 cur1++ 即可！

• 如果 nums[cur1] > nums[cur2] 的话：

  • 这种情况就能快速处理逆序对，因为此时 nums[cur1] 大于 nums[cur2]，且因为两个区间都是升序的，所以 [cur1, mid] 都是大于 nums[cur1]，那么不就得到 [cur1, mid] 区间的元素都大于 nums[cur2] 了吗，所以我们可以直接通过下标来得到区间的元素个数，即 mid - cur1 + 1 就是这个区间的元素，它们都是大于后面的区间的 nums[cur2] 的！
    • 并且区间 [cur1, mid] 是在左区间的，而 nums[cur2] 是在右区间的，在没有合并这两个区间之前，它们在数组中的前后位置相当于是没变的，所以这是符合题目要求说的数字要大于的是后面的数字！不会说导致这些大于 nums[cur2] 的数是在它后面的而导致和题目要求不符！

  

  • 此外，当降序的时候这种找比该值之前大的元素的情况就不适合了，因为如果是降序的话，那么 nums[cur1] > nums[cur2] 的话，此时虽然 [left, cur1] 区间的元素都是符合大于 nums[cur2] 的，但是如果 cur1++ 了之后，nums[cur1] 还是大于 nums[cur2] 的话，那么此时 [left, cur1] 区间的元素就相当于被重复累加了一遍，就错误了！（降序的情况下一个思路讨论）

​ 上面两种情况总结起来就是下图：

class Solution {
public:int reversePairs(vector<int>& nums) {vector<int> tmp(nums.size());return merge_sort(nums, 0, nums.size() - 1, tmp);}int merge_sort(vector<int>& nums, int left, int right, vector<int>& tmp){if(left >= right)return 0;int ret = 0;// 先分治int mid = (left + right) >> 1;ret += merge_sort(nums, left, mid, tmp);ret += merge_sort(nums, mid + 1, right, tmp);// 再进行选值拷贝到tmp，并且最后进行合并处理int i = left;int cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right){// 其中拷贝的过程中进行对逆序对的判断，重点就在这里！！！if(nums[cur1] <= nums[cur2])tmp[i++] = nums[cur1++];else{ret += (mid - cur1 + 1);tmp[i++] = nums[cur2++];}}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];while(left <= right){nums[left] = tmp[left];left++;}return ret;}
};

思路二：寻找比该值之后小的元素个数

​ 上面我们讲过，思路一的情况对于降序的话，是不成立的，因为会重复累加那个大于该值的区间多次，导致错误！所以我们可以变更一下思路，这里也是相当于是一个思路拓展，上面的方法是完全能够解决的了，这里只是对上面思路的一个另一种情况讨论，思路其实都差不多！

​ 因为此时数组是降序的情况了，那我们就想，本来题目要我们找的是前面数字大于后面数字的情况，那反过来，不就变成了找后面数字小于前面数字的情况吗，对不对！

​ 这个思路转化对降序来说非常的重要，看看下面的讨论就知道了，下面依然是用左右区间来讨论：

• 如果 nums[cur1] <= nums[cur2] 的话：
  • 此时因为区间都是升序的（包括等于），这种情况下找不到能快速处理逆序对的情况，所以直接 让 nums[cur2] 拷贝到临时数组中，并让 cur2++ 即可！
• 如果 nums[cur1] > nums[cur2] 的话：
  • 这种情况就能快速处理逆序对，因为此时 nums[cur1] 大于 nums[cur2]，且因为两个区间都是降序的，所以 [cur2, right] 都是要小于 nums[cur2] 的，那么不就得到 [cur2, right] 区间的元素都大于 nums[cur1] 了吗，所以我们可以直接通过下标来得到区间的元素个数，即 right - cur2 + 1 就是这个区间的元素，它们都是小于前面区间的 nums[cur1] 的！

class Solution {
public:int reversePairs(vector<int>& nums) {vector<int> tmp(nums.size());return merge_sort(nums, 0, nums.size() - 1, tmp);}int merge_sort(vector<int>& nums, int left, int right, vector<int>& tmp){if(left >= right)return 0;int ret = 0;int mid = (left + right) >> 1;ret += merge_sort(nums, left, mid, tmp);ret += merge_sort(nums, mid + 1, right, tmp);int i = left;int cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right){// 变的只有这部分！！！if(nums[cur1] <= nums[cur2])tmp[i++] = nums[cur2++];else{ret += (right - cur2 + 1);tmp[i++] = nums[cur1++];}}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];while(left <= right){nums[left] = tmp[left];left++;}return ret;}
};