【大厂算法笔试题 | 13】归并排序引出的系列问题（小和、逆序对、特定逆序对）

1、数组的小和

什么是小和？

设 array为一个有n个数字的数组(n>1)。如果存在正整数 i，j，使得 0 ≤ i ≤ j ≤ n-1 且 array[i] < array[j]，则针对数组中每个位置的 j，所有满足条件的i位置的数字 之和为j位置的小和，所有j位置的小和 累加则为数组的小和。

例如：数组(3,1,4,5,2)的小和组成：

1. 对于数字3：没有小和
2. 对于数字1：没有小和
3. 对于数字4，小和为：3 + 1 = 4；
4. 对于数字5，小和为：3 + 1 + 4 = 8；
5. 对于数组2，小和为：1；
6. 所以对于整个数组，小和为：0 + 0+ 4 + 8 + 1 = 13；

1）思路

先找出每个数字num的右边有多少个数（count）比它大，则数组的小和可以表示为 数组中每个数字的（num * count）累加之和。

暴力解法的时间复杂度为O(n^2)，而在归并排序的过程中找到，时间复杂度仅为O(nlogn)，因此在归并排序的过程去找到所有的小和。

2）代码

public static int smallSum(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int n = arr.length;
    int[] temp = new int[n];

    return sort(arr, 0, n - 1, temp);
}

private static int sort(int[] arr, int left, int right, int[] temp) {
    if (left >= right) {
        return 0;
    }
    int mid = left + (right - left) / 2;
    return sort(arr, left, mid, temp)
            + sort(arr, mid + 1, right, temp)
            + merge(arr, left, mid, right, temp);
}

private static int merge(int[] arr, int left, int mid, int right, int[] temp) {
    int pLeft = left;
    int pRight = mid + 1;
    int t = 0;
    // 小和
    int res = 0;
    while (pLeft <= mid && pRight <= right) {
        // 找出右序列中比左序列中某个数字大的数字个数count，res累加arr[pLeft] * count
        res += arr[pLeft] < arr[pRight] ? (right - pRight + 1) * arr[pLeft] : 0;
        temp[t++] = arr[pLeft] <= arr[pRight] ? arr[pLeft++] : arr[pRight++];
    }
    while (pLeft <= mid) {
        temp[t++] = arr[pLeft++];
    }
    while (pRight <= right) {
        temp[t++] = arr[pRight++];
    }

    t = 0;
    while (left <= right) {
        arr[left++] = temp[t++];
    }
    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
41
42
43
44

2、逆序对

什么是逆序对？

设 array为一个有n个数字的数组(n>1)。如果存在正整数i，j使得 0 ≤ i < j≤ n-1 且 array[i] > array[j]。则这两个数 称为array的一个逆序对，也称作逆序数。

例如：数组(3,1,4,5,2)的逆序对有(3,1)，(3,2)，(4,2)，(5,2)；一共4个逆序对。

简言之，逆序对就是数组中任意两个数满足大的在前,小的在后的组合。

1）思路

在归并排序的过程中，每次都会将左序列 和 右序列中的数对比，只需要在每次对比时 统计左序列中的某个数字 比 右序列中几个数字大，将数字个数累加到结果上即可。

整体时间复杂度只为O(nlogn)，而暴力解法的时间复杂度为O(n^2)。

2）代码

public static int reversePairs(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int n = arr.length;
    int[] temp = new int[n];

    return sort(arr, 0, n - 1, temp);
}

private static int sort(int[] arr, int left, int right, int[] temp) {
    if (left >= right) {
        return 0;
    }
    int mid = left + (right - left) / 2;
    return sort(arr, left, mid, temp)
            + sort(arr, mid + 1, right, temp)
            + merge(arr, left, mid, right, temp);
}

private static int merge(int[] arr, int left, int mid, int right, int[] temp) {
    int pLeft = mid;
    int pRight = right;
    int t = 0;
    // 逆序对个数
    int res = 0;
    while (pLeft >= left && pRight >= mid + 1) {
        // 找出左序列的数 比 右序列中的几个数大
        res += arr[pLeft] > arr[pRight] ? (pRight - mid) : 0;
        temp[t++] = arr[pLeft] > arr[pRight] ? arr[pLeft--] : arr[pRight--];
    }
    while (pLeft >= left) {
        temp[t++] = arr[pLeft--];
    }
    while (pRight >= mid + 1) {
        temp[t++] = arr[pRight--];
    }

    t = 0;
    while (right >= left) {
        arr[right--] = temp[t++];
    }
    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
41
42
43
44

3、特定逆序对

什么是特定逆序对？

数组中每个位置的数字num 的右边数(rightNum) * 2 < num 的数字 个数之和。这里的2 可以是任意数。

例如：数组(3, 1, 13, 19, 7, 2, 5)的特定逆序对组成：

1. 对于数字3：特定逆序对为：(3,1)
2. 对于数字1：没有特定逆序对
3. 对于数字13，特定逆序对为：(13,2)，(13,5)
4. 对于数字19，特定逆序对为：(19,7)，(19,2)，(19,5)
5. 对于数字7，特定逆序对为：(7,2)
6. 对于数字2，没有特定逆序对
7. 对于数字5，没有特定逆序对
8. 所以对于整个数组，特定逆序对有：(3,1)，(13,2)，(13,5)，(19,7)，(19,2)，(19,5)，(7,2)；一共7个。

1）思路

在归并排序的过程中，每次都会将左序列 和 右序列中的数对比，只需要在每次对比时 统计左序列中的某个数字 比 右序列中几个数字 * 2大，将数字个数累加到结果上即可。

整体时间复杂度只为O(nlogn)，而暴力解法的时间复杂度为O(n^2)。

2）代码

public static int reversePairs(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int n = arr.length;
    int[] temp = new int[n];

    return sort(arr, 0, n - 1, temp);
}

private static int sort(int[] arr, int left, int right, int[] temp) {
    if (left >= right) {
        return 0;
    }
    int mid = left + (right - left) / 2;
    return sort(arr, left, mid, temp)
            + sort(arr, mid + 1, right, temp)
            + merge(arr, left, mid, right, temp);
}

private static int merge(int[] arr, int left, int mid, int right, int[] temp) {

    int res = 0;
    // 符合条件的数集：[M+1, windowR)，windowR是到不了的数字
    int windowR = mid + 1;
    for ( int i = left; i <= mid; i ++) {
        // 因为左半边序列也是有序的，所以左序列中下一个数一定arr[windowR] * 2 大，所以不需要重置windowR
        while (windowR <= right && arr[i] > (arr[windowR] * 2)) {
            windowR ++;
        }
        res += windowR - mid - 1;
    }

    int pLeft = left;
    int pRight = mid + 1;
    int t = 0;
    while (pLeft <= mid && pRight <= right) {
        temp[t++] = arr[pLeft] <= arr[pRight] ? arr[pLeft++] : arr[pRight++];
    }
    while (pLeft <= mid) {
        temp[t++] = arr[pLeft++];
    }
    while (pRight <= right) {
        temp[t++] = arr[pRight++];
    }

    t = 0;
    while (left <= right) {
        arr[left++] = temp[t++];
    }
    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
41
42
43
44
45
46
47
48
49
50
51
52