详解归并排序及其应用

912. 排序数组

315. 计算右侧小于当前元素的个数

493. 翻转对

327. 区间和的个数

排序算法千千万，今天先讲归并！！

算法思想

「归并排序」其实是一种分而治之的思想。需要把 10 个数字排好序，先分一半，各自排好后，然后合并。简而言之：先分后治

看了这个图，是不是感觉就是一棵树的后续遍历过程，详情可见 二叉树--纲领篇

现在来分析一下「归并排序」的时间复杂度

对于长度为n的数组来说，在「分」的过程中，会构建出如上图所示的一棵树，其高度为logN，每一层均有n个节点

在「治」的过程中，每一层就是合并两个有序数组，其时间复杂度为o(N)

所以最终时间复杂度为o(nlogn)

算法框架

xxxxxxxxxx
public class MergeSort {

    private int[] temp;

    public void sort(int[] nums) {
        temp = new int[nums.length];
        sort(nums, 0, nums.length - 1);
    }
    // 分
    private void sort(int[] nums, int lo, int hi) {
        if (lo == hi) return ;
        int mid = lo - (lo - hi) / 2;
        sort(nums, lo, mid);
        sort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }
    // 治
    // 等价于两个有序数组合并 [lo..mid] 和 [mid+1..hi]
    private void merge(int[] nums, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) temp[i] = nums[i];
        int cnt = lo;
        int i = lo, j = mid + 1;
        while (i <= mid || j <= hi) {
            if (i > mid) nums[cnt++] = temp[j++];
            else if (j > hi) nums[cnt++] = temp[i++];
            else if (temp[i] <= temp[j]) nums[cnt++] = temp[i++];
            else nums[cnt++] = temp[j++];
        }
    }
} 

算法应用

最简单的应用肯定就是给一个数组，然后排序。如题目 排序数组

今天来介绍几个难「亿」点的题目

计算右侧小于当前元素的个数

题目详情可见 计算右侧小于当前元素的个数

这个题目可以直接用暴力，但是想都不用想，绝对超时！！

我们可以利用「归并排序」的特性，在「合并」的时候，两边各自有序，且相对位置固定

我们抽取一个「治」的子过程：

可以看到两边各自有序，且[2,5,6,7]一定处于原数组下标为0-3的位置，而[1,3,4,9]一定处于原数组下标为4-7的位置

所以[2,5,6,7]右边的元素就是[1,3,4,9]

假设此时处于上图所示的时刻，即：1,2,3,4已经排好序，i处于5的位置，j处于9的位置

由于5 < 9，所以i需要向前移动一格，同时，我们可以知道右边比5小的元素有3个，即：1,3,4

总结一下：每次i向前移动一格，就可以知道右边比i位置小的元素个数

现在还有另外一个问题，在移动的过程中，每个元素的原下标早已改变，比如元素5原来处于下标0的位置，现在变到了1的位置

所以，我们需要定一个一个新的数据结构，记录每个元素和原下标的对应关系

下面请看详细代码：

xxxxxxxxxx
// 记录每个元素和原下标的对应关系
class Pair {
    int val, id;
    public Pair(int val, int id) {
        this.val = val;
        this.id = id;
    }
}
private Pair[] temp;
// 记录每个数右边元素小于的数量
private int[] count;
public List<Integer> countSmaller(int[] nums) {
    int n = nums.length;
    count = new int[n];
    temp = new Pair[n];
    Pair[] arr = new Pair[n];
    // 构建 Pair[]
    for (int i = 0; i < n; i++) arr[i] = new Pair(nums[i], i);
    
    sort(arr, 0, n - 1);
    
    // int[] -> List
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) ans.add(count[i]);
    return ans;
}
private void sort(Pair[] arr, int lo, int hi) {
    if (lo == hi) return ;
    int mid = lo - (lo - hi) / 2;
    sort(arr, lo, mid);
    sort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
}
private void merge(Pair[] arr, int lo, int mid, int hi) {
    for (int i = lo; i <= hi; i++) temp[i] = arr[i];
    int index = lo;
    int i = lo, j = mid + 1;
    while (i <= mid || j <= hi) {
        if (i > mid) arr[index++] = temp[j++];
        // i 要向前移动一格
        else if (j > hi) {
            count[temp[i].id] += j - mid - 1;
            arr[index++] = temp[i++];
        }
        else if (temp[i].val > temp[j].val) arr[index++] = temp[j++];
        // i 要向前移动一格
        else {
            count[temp[i].id] += j - mid - 1;
            arr[index++] = temp[i++];
        }
    }
}

翻转对

题目详情可见 翻转对

我们可以维护一个区间：

• 对于左边为2时，右边满足情况的区间为空
• 对于左边为5时，右边满足情况的区间为[1]
• 对于左边为6时，右边满足情况的区间为空[1]
• 对于左边为7时，右边满足情况的区间为空[1, 3]

可以知道对于满足6的区间，肯定也满足7。所以每次判断下一个数时，只需要进行区间扩张即可！！

下面请看详细代码：

xxxxxxxxxx
private int[] temp;
private int ans = 0;
public int reversePairs(int[] nums) {
    int n = nums.length;
    temp = new int[n];
    sort(nums, 0, n - 1);
    return ans;
}
private void sort(int[] nums, int lo, int hi) {
    if (lo == hi) return ;
    int mid = lo - (lo - hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);
    merge(nums, lo, mid, hi);
}
private void merge(int[] nums, int lo, int mid, int hi) {
    for (int i = lo; i <= hi; i++) temp[i] = nums[i];
    // 右边区间从 mid + 1 开始
    int end = mid + 1;
    for (int i = lo; i <= mid; i++) {
        // 向右扩张区间
        while (end <= hi && (long) nums[i] > (long) nums[end] * 2) end++;
        // 计算满足条件数量
        ans += end - mid - 1;
    }
    int index = lo;
    int i = lo, j = mid + 1;
    while (i <= mid || j <= hi) {
        if (i > mid) nums[index++] = temp[j++];
        else if (j > hi) nums[index++] = temp[i++];
        else if (temp[i] > temp[j]) nums[index++] = temp[j++];
        else nums[index++] = temp[i++];
    }
}

区间和的个数

题目详情可见 区间和的个数

一开始看到这个题目，下意识的想用「滑动窗口」，滑动窗口相关文章可见 滑动窗口技巧 和 子数组之滑动窗口篇

可是可是可是...这里不能用「滑动窗口」，为什么呢？因为滑动窗口必须具有单调性，这个题目一会「➕」一会「➖」

由于题目需要求在[lower, upper]范围内的所有子数组数量，所以可以把问题转化成对「前缀和」归并排序的过程中计算满足要求数量

有人可能会问，前缀和不就是递增的嘛？还需要排啥序呀！！不不不，仔细看这个题目中有正有负，所以前缀和不一定递增

我们可以维护一个区间：对于的一个元素x，先找到右边的下界，然后找到右边的上届，假设满足区间为[a, b]

对于下一个元素y，一定满足x <= y且右边的下界一定>= a，右边的上界一定>= b

根据上述特点，给出详细代码：

xxxxxxxxxx
private long[] temp;
private int ans = 0;
private int lower, upper;
public int countRangeSum(int[] nums, int lower, int upper) {
    temp = new long[nums.length + 1];
    this.lower = lower;
    this.upper = upper;
    long[] preSum = new long[nums.length + 1];
    // 求前缀和
    for (int i = 1; i < preSum.length; i++) preSum[i] = preSum[i - 1] + nums[i - 1];
    sort(preSum, 0, preSum.length - 1);
    return ans;
}
private void sort(long[] nums, int lo, int hi) {
    if (lo == hi) return ;
    int mid = lo - (lo - hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);
    merge(nums, lo, mid, hi);
}
private void merge(long[] nums, int lo, int mid, int hi) {
    for (int i = lo; i <= hi; i++) temp[i] = nums[i];
    
    // 最初上下界均为 mid + 1
    int start = mid + 1, end = mid + 1;
    for (int i = lo; i <= mid; i++) {
        // 确定下界
        while (start <= hi && nums[start] - nums[i] < lower) start++;
        // 确定上界
        while (end <= hi && nums[end] - nums[i] <= upper) end++;
        // 计算满足条件数量
        ans += end - start;
    }

    int cnt = lo;
    int i = lo, j = mid + 1;
    while (i <= mid || j <= hi) {
        if (i > mid) nums[cnt++] = temp[j++];
        else if (j > hi) nums[cnt++] = temp[i++];
        else if (temp[i] >= temp[j]) nums[cnt++] = temp[j++];
        else nums[cnt++] = temp[i++];
    }
}