归并排序：解决小和、逆序对问题 一、小和问题 二、逆序对问题

发表于

大家好，我是周一。

在上一篇归并排序中，我们讲了归并排序的基本概念、merge（合并）过程等，今天趁热打铁，我们来说说使用归并排序的一些常见面试题。

一、小和问题

1、题目描述：

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

2、例子：

数组为：[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

3、思路：

找每一个数右边比当前数大的个数，(个数 * 当前数) 的累加和就是结果。

这咋和归并排序联系上的呢，仔细想想，在左组和右组merge的时候，会比较数的大小，这时就可以在右组找到比左组当前数大的个数。

4、详细的参考代码：

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
java复制代码/**
 * 小和问题：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。要求时间复杂度O(N*logN) 
 *
 * @author Java和算法学习：周一
 */
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) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        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 pL = l;
        int pR = mid + 1;
        int res = 0;
        while (pL <= mid && pR <= r) {
            // 当左组的数小于右组的数时， 当前右组的个数*当前数 的累加和 即是小和的结果
            // 仔细和归并排序比较，发现就多了此处的代码。唯一的区别是，
            // 等于的时候拷贝右组的，因为要在右组中找出比左组大的个数，肯定不能先拷贝左组的，不然咋找出个数
            res += arr[pL] < arr[pR] ? (r - pR + 1) * arr[pL] : 0;
            help[i++] = arr[pL] < arr[pR] ? arr[pL++] : arr[pR++];
        }
        while (pL <= mid) {
            help[i++] = arr[pL++];
        }
        while (pR <= r) {
            help[i++] = arr[pR++];
        }

        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
        return res;
    }

    /**
     * 对数器方法
     */
    public static int comparator(int[] arr) {
        int res = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                res += arr[j] < arr[i] ? arr[j] : 0;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int maxSize = 100;
        int maxValue = 100;
        int testTimes = 100000;

        boolean isSuccess = true;
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = generateArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (smallSum(arr1) != comparator(arr2)) {
                printArray(arr1);
                printArray(arr2);
                isSuccess = false;
                break;
            }
        }
        System.out.println(isSuccess ? "Nice" : "Error");
    }

    //------------------------------------------ TEST METHODS ----------------------------------------------

    public static int[] generateArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

}

二、逆序对问题

1、题目描述：

设有一个数组 [a1, a2, a3,… an]，对于数组中任意两个元素ai，aj，若i<j，ai>aj，则说明ai和aj是一对逆序对。求一个给定数组的逆序对个数。

2、例子：

3 5 2 1 0 4 9

所有逆序对是：(3,2)，(3,1)，(3,0)，(5,2)，(5,1)，(5,0)，(5,4)，(2,1)，(2,0)，(1,0)。逆序对个数为10。

3、思路：

合并的时候，从右往左合并，(此时右组位置 - mid位置) 的累加和 即是逆序对个数。

这又咋和归并排序联系上的呢，仔细想想，在左组和右组merge的时候，会比较数的大小，但是我要找到的是右边更小的，所以可以采用从右往左合并的方式；同时在处理相等的时候，需要先拷贝右组的，这样才能准确找出右组小的个数。

4、详细的参考代码：

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
java复制代码/**
 * 逆序对问题：设有一个数组 [a1, a2, a3,... an]，对于数组中任意两个元素ai，aj，若i<j 且 ai>aj，则说明ai和aj是一对逆序对。
 * 求一个给定数组的逆序对个数。
 *
 * @author Java和算法学习：周一
 */
public class ReversePair {

    public static int reversePairNum(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) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        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 = help.length - 1;

        // 同理，左组第一个数位置为mid
        int pL = mid;
        // 右组第一个数为最后一个
        int pR = r;
        // 逆序对个数
        int num = 0;
        while (pL >= l && pR >= (mid + 1)) {
            // 找到右组第一个比左组小的数，则当前满足要求的逆序对个数为 (pR - (mid + 1) + 1) 即是 (pR - mid)
            num += arr[pL] > arr[pR] ? (pR - mid) : 0;
            // 从右往左拷贝，相等的拷贝右组的
            help[i--] = arr[pL] > arr[pR] ? arr[pL--] : arr[pR--];
        }
        // 左组和右组有且仅有一个未拷贝完，所以以下两个循环只会执行其中一个
        while (pL >= l) {
            help[i--] = arr[pL--];
        }
        while (pR > mid) {
            help[i--] = arr[pR--];
        }

        // 拷贝回原数组
        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
        return num;
    }

    /**
     * 对数器用于测试
     */
    public static int comparator(int[] arr) {
        int num = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[i]) {
                    num++;
                }
            }
        }
        return num;
    }

    public static void main(String[] args) {
        int testTime = 1000000;
        int maxSize = 100;
        int maxValue = 100;

        boolean isSuccess = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (reversePairNum(arr1) != comparator(arr2)) {
                printArray(arr1);
                printArray(arr2);
                isSuccess = false;
                break;
            }
        }
        System.out.println(isSuccess ? "Nice" : "Error");
    }

    //--------------------------------------- 辅助测试的方法 ---------------------------------------------

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }

        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }

        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

}

OK，今天就暂时先说利用归并排序解决小和和逆序对问题的题目。

有时候，各种排序算法掌握它本身并不难，难的是你能够充分理解它的过程和精髓，更难的是在真正遇到实际题目的时候，能够想到用这种排序算法来解决它。所以，算法无捷径，唯有多练习，在有足够多的量，积累量变，然后才能迎来质变，那时才能信手拈来，加油。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%