0%

小和与逆序对问题

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

小和问题

在一个数组中， 每一个数左边比当前数小的数累加起来， 叫做这个数组的小和。 求一个数组的小和。
例子：
[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小于2，那么1一定小于2即其后的所有元素（因为前后两半数组已排好序）,那么小和中一定有R - j + 1个元素1。当归并排序处于如下过程时，会产生小和：

同理，我们可以得出有R - j + 1个3。

小和问题的代码如下：

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
32
33
34
35
36
37
38
39
40
//最小和问题
public class SmallSum {

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

    private static int mergeSortCore(int[] arr, int L, int R) {
        if (L == R)
            return 0;
        // 相比于(L + R) / 2，下面的更快且避免整型溢出
        int mid = L + ((R - L) >> 1);
        return mergeSortCore(arr, L, mid) + mergeSortCore(arr, mid + 1, R) + merge(arr, L, R, mid);
    }

    private static int merge(int[] arr, int L, int R, int mid) {
        int[] help = new int[R - L + 1];
        int k = 0;// 指向数组help的指针
        int i = L;
        int j = mid + 1;
        int res = 0;
        while (i <= mid && j <= R) {
            res += arr[j] > arr[i] ? arr[i] * (R - j + 1) : 0;//计算小和
            help[k++] = arr[j] <= arr[i] ? arr[j++] : arr[i++];
        }

        while (i <= mid)
            help[k++] = arr[i++];

        while (j <= R)
            help[k++] = arr[j++];

        for (int u = 0; u < help.length; u++)
            arr[L + u] = help[u];

        return res;
    }
}

逆序对问题

在一个数组中， 左边的数如果比右边的数大， 则两个数构成一个逆序对， 请统计所有逆序对数。
逆序对问题其实和小和问题基本上是一样的，只是这里的比较标准是左边的数大于右边的数，而小和问题是左边的数要小于右边的数才能产生小和。
逆序对的代码如下：

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
32
33
34
35
36
37
38
39
40
//逆序对问题
public class InversionPair {

    public static int InversePairs(int[] array) {
        if (array == null || array.length < 2)
            return 0;
        return inversionPairCore(array, 0, array.length - 1);
    }

    private static int inversionPairCore(int[] arr, int L, int R) {
        if (L == R)
            return 0;
        int mid = L + ((R - L) >> 1);//注意括号
        int leftPairs = inversionPairCore(arr, L, mid);
        int rightPairs = inversionPairCore(arr, mid + 1, R);
        return (leftPairs + rightPairs + merge(arr, L, R, mid));
    }

    private static int merge(int[] arr, int L, int R, int mid) {
        int[] help = new int[R - L + 1];
        int k = 0;
        int i = L;
        int j = mid + 1;
        int pairNum = 0;
        while (i <= mid && j <= R) {
            pairNum += arr[i] > arr[j] ? mid - i + 1 : 0;
            help[k++] = arr[j] < arr[i] ? arr[j++] : arr[i++];
        }

        while (i <= mid)
            help[k++] = arr[i++];

        while (j <= R)
            help[k++] = arr[j++];

        for (int u = 0; u < help.length; u++)
            arr[L + u] = help[u];
        return pairNum;
    }
}
------ 本文结束------