左程云算法与数据结构课 https://www.bilibili.com/video/BV13g41157hK?p=2&spm_id_from=pageDriver

小和问题

在一个数组中，每个数左边比当前数小的数累加起来，叫做这个数组的小和。

例如：[1,3,4,2,5]，1左边比1小的数，没有；3左边比3小的数，1；4左边比4小的数，1、3；2左边比2小的数，1；5左边比5小的数，1、3、4、2。所以小和为1+1+3+1+1+3+4+2=16。

题解

小和问题也可以按如下方法求，看每个数右边有多少个比它大的数，那这个数就累加几次。

例如：[1,3,4,2,5]，1右边比1大的数有4个；3右边比3大的数有两个；4右边比4大的数有1个；2右边比2大的数有1个；5右边没有比5大的数。所以小和为1*4 + 3*2 + 4*1 + 2*1 =16。

可以通过归并排序的思想求小和问题。设变量res=0，

1 和 3 比较。1 比 3 小，所以 res =res+1，{1}。 归并结果为{1,3}。

{1,3} 和 4 比较。1 比 4 小，所以 res=res+1，{1}；3 比 4 小，所以res =res+3，{1,3}。归并结果为{1,3,4}。

2 和 5 比较。2 比 5 小，所以 res=res+2，{2}。归并结果为{2,5}。

{1,3,4} 和 {2,5} 比较。1 比 2小，因为右部份是有序的，所以1 比 右部分所有数(2,5两个数)都小，所以 res = res + 1*2，{1}；3 比 2 大，{1,2}；3 比 5 小，所以 res=res+3，{1,2,3}；4 比 5 小，所以res=res+4，{1,2,3,4}。归并结果为{1,2,3,4,5}。

最后res的值即为数组的小和。

代码实现

public class SmallSum {
    //求数组小和
    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0 , arr.length - 1);
    }
    //用归并排序的思想求数组小和
    private static int process(int[] arr, int l, int r) {
        if (l == r) { //只有一个元素即小和为0
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        //小和等于左部分小和+右部分小和+merge过程小和
        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
    }
    private static int merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1]; //辅助数组
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        int res = 0; //小和
        while (p1 <= mid && p2 <= r) {
            //当左侧数比右侧数小时，左侧数是所有右侧数的小和需要累加的值
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            //与经典merge的区别是当两数相等时取右侧数，否则会导致小和不正确
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return res;
    }

    //for test
    public static void main(String[] args) {
        int[] arr = {1,3,4,2,5};
        System.out.println(smallSum(arr));
    }
}

逆序对问题

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有的逆序对。

例如：[3,2,4,5,0] 的全部逆序对是 (3,2)、(3,0)、(2,0)、(4,0)、(5,0)

题解

经过小和问题的熏陶，我们很容易想到逆序对问题也可以通过归并排序的思想求得。只不过小和问题是左侧数比右侧小时进行相应处理，而逆序对问题是左侧数比右侧数大时进行相应处理。

代码

public class InversionPair {

    public static void inversionPair(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        process(arr, l, mid);
        process(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r -l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r) {
            if (arr[p1] > arr[p2]) { //左部分有序，若其比右侧值大，则其后所有值均比右侧值大
                int temp = 0;
                while (temp < mid - p1 + 1) { //输出逆序对
                    System.out.println("(" + arr[p1 + temp] + "," + arr[p2] +")");
                    temp++;
                }
            }
            //注意此处是<=,即两数相等时取左侧数，若取右侧数，则当左部分有比右侧数大的值时，就会遗漏逆序对
            //与小和问题的此处 < 对比思考
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }

    //for test
    public static void main(String[] args) {
        int[] arr = {3,2,4,3,0};
        inversionPair(arr);
    }
}