【分治】数组中的逆序对
【分治】数组中的逆序对
剑指 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;
}
};腾讯云开发者
