英雄算法7月24号

Offer 51

class Solution {
    int cnt = 0;
public:
    int reversePairs(vector<int>& nums) {
        int len = nums.size();
        vector<int> tmp(len, 0);
        mergeSort(nums, tmp, 0, len - 1);
        return cnt;
    }
    void mergeSort(vector<int>& nums, vector<int>& tmp, int L, int R) {
        if(L < R) {
            int mid = (L + R) >> 1;
            mergeSort(nums, tmp, L, mid);
            mergeSort(nums, tmp, mid + 1, R);
            merge(nums, tmp, L, R);
        } 
    }
    void merge(vector<int>& nums, vector<int>& tmp, int lef, int rig) {
        int mid = (lef + rig) >> 1, L = lef, R = mid + 1, k = L;
        while(L <= mid && R <= rig) {
            if(nums[R] < nums[L]) { 
                cnt += mid - L + 1;//在归并的基础上，加了这段话：用于求解左区间内，和nums[R]构成逆序对的个数 
                tmp[k++] = nums[R++]; 
            }
            else tmp[k++] = nums[L++];
        }
        while(L != mid + 1) tmp[k++] = nums[L++];
        while(R != rig + 1) tmp[k++] = nums[R++]; 
        for(int i = lef; i <= rig; ++i) nums[i] = tmp[i];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

思路

归并排序

我们对归并过程中的一段数组来分析：由于是归并排序，所以数组左右两端的子数组都是有序的（本题，我们使用的是升序）。

下面，我们给出例子讲解：

---

如图，我们有一段数组，元素为7 9 1 3。现在，我们对其进行merge操作。两个指针分别指向两个区间的两端。我们可以很轻易的发现，左指针指向的7， 大于 右指针指向的1。又由于左区间是升序，因此从左指针开始，一直到左区间结束的所有元素都大于1。这些元素均和1构成逆序对，所以ans += 左指针 到 左区间末尾 元素的个数。

---

现在，右指针右移，并对1做出排序。现在对左右指针指向元素进行比较，发现7 > 3。因此ans += len ==> ans = 4

---

现在，不存在逆序对，因此ans不会改变，结束比较

---

现在，我们回看整个过程

我们所做的是在左区间寻找 能和 右区间元素 构成逆序对 的 对数。因为左区间是有序的，只要找到一个数大右区间遍历的那个数，那么剩下的元素都满足条件，这极大的加速了逆序对个数的求解。就像上述过程中，我们寻找和1构成逆序对的个数。在左区间找到7，就知道左区间大于等于7的元素都可以和1构成逆序对了

现在，我们提出几个问题

• 为什么只寻找和右区间元素构成逆序对的对数?左区间元素不管嘛?
• 左区间元素顺序和原数组顺序不同，难道不会影响结果嘛？

现在，我们给出解答

• 对于问题1，我们要知道，归并的思想是分而治之。虽然我们给出的例子中，merge操作一直是在统计 左区间内 和 右区间元素构成逆序对的对数。但是我们要知道，左区间也可以被拆分为 左区间的左区间， 左区间的右区间；也就是说，左区间已经比较完了！所以，不是不管左区间，而是左区间已经比较完成，无需重复考虑
• 对于问题2，本质上和问题1是一致的。我们在merge操作时求解逆序对，左区间已经求解完毕，无论左区间是何种顺序，都不会影响对于右区间元素统计逆序对的个数
  • eg: 对于例子中的数组 7 9 1 3；我们将左区间打乱顺序，更改为 9 7 1 3。我们可以发现，和1构成逆序对的个数还是2个，左区间内 9 和 7 都可以和 1构成逆序对。因此，左区间的顺序不会影响逆序对个数；左区间顺序只会影响求解速度。（因为左区间无序，我们不知道9后面的元素大小，因此不能判断9后面的元素是否能和1构成逆序对，我们需要遍历它，才能判断）

有了上述解释，代码也就不难书写。核心就是归并排序。在排序的过程中，比较右区间和左区间元素大小。

这里我们给出归并排序的代码

//因为归并练习的时候在学习Java，所以就用Java写了，没有C++版本，淦！
class Solution {
    public int[] sortArray(int[] nums) {
        int[] tmp = new int[nums.length];
        mergeSort(nums, tmp, 0, nums.length - 1);
        return tmp;
    }
    public void mergeSort(int[] nums, int[] tmp, int lef, int rig) {
        if(lef < rig) {
            int mid = (lef + rig) >> 1;
            mergeSort(nums, tmp, lef, mid);
            mergeSort(nums, tmp, mid + 1, rig);
            merge(nums, tmp, lef, rig);
        }
    }
    public void merge(int[] nums, int[] tmp, int lef, int rig) {
        if(lef >= rig) return;
        int mid = (lef + rig) >> 1, l = lef, r = mid + 1, k = lef;
        while(l != mid + 1 && r != rig + 1) {
            if(nums[l] < nums[r]) tmp[k++] = nums[l++];
            else tmp[k++] = nums[r++];
        }
        while(l != mid + 1) tmp[k++] = nums[l++]; 
        while(r != rig + 1) tmp[k++] = nums[r++];
        for(int i = lef; i <= rig; ++i) nums[i] = tmp[i];    
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27