算法题目— — 归并排序的应用

1 递归排序代码

递归排序流程

• mergeSort(int[] arr)
• process(int[] arr, int L, int R);
• merge(int[] arr, int L, int M, int R)

package com.ali.test;


import java.util.Arrays;

public class MergeSortTest {
    public static void main(String[] args) {
        int[] arr = {3,5,1,5,1,6,62,0,80,-1,41,5108,54180,84,-45180,15,64};
        int[] arr2 = {3,5,1,5,1,6,62,0,80,-1,41,5108,54180,84,-45180,15,64};
        Arrays.sort(arr);
        print(arr);
        System.out.println();
        mergeSort(arr2);
        print(arr2);
    }
    //归并排序[递归方法实现]
    public static void mergeSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        process(arr, 0, arr.length - 1);

    }
    public 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);
    }

    //合并
    public static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];//临时数组
        int i = 0;
        //定义两个指针，指向两个不同半区
        int p1 = L;
        int p2 = M + 1;
        while(p1 <= M && p2 <= R){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //有一个越界
        while(p1 <= M){
            help[i++] = arr[p1++];
        }
        while(p2 <= R){
            help[i++] = arr[p2++];
        }
        for(i = 0; i < help.length; ){
            arr[L++] = help[i++];
        }

    }


    public static void print(int[] arr){
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

}

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

2 递归排序应用

2.1 小和问题

在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。

例子： [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

主要思路：在递归排序的基础上，if (arr[p1] < arr[p2]) then res+= arr[p1]* (R - p2 + 1) ,否则res+=0
代码：

package com.ali.test;

public class SmallSumTest {

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

    /**
     * arr[L, R]既要排好序，也要求小和返回
     * 所有merge时，产生的小和，累加
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public 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);
    }
    public static int merge(int[] arr, int L, int M, int R){
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        int res = 0;//记录小和
        while(p1 <= M && p2 <= R){
            //关键步骤：
            //L: 1 3 7 8
            //R: 1 2 4 9
            //(R - p2 + 1) * arr[p1] 左边总共小的数的sum
            //等于的话，走右边
            res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= M){
            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 int comparator(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        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;
    }

    // for test
    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 * Math.random());
        }
        return arr;
    }

    // for test
    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;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (smallSum(arr1) != comparator(arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }
}

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

2.2 求数组中所有逆序对

思路:
和上面小和问题类似，只不过是反过来遍历数组
int p1 = M;
int p2 = R;
while(p1 >= L && p2 > M){
    res += arr[p1] > arr[p2] ? (p2 - M) : 0;
…
}

package com.ali.math.class_04;

public class ReversePairTest {

    /**
     * 求逆序对
     * @param arr
     * @return
     */
    public static int reversePairNum(int[] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    /**
     * arr[L, R]既要排好序，也要对逆序对数量进行返回
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public 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);
    }
    public static int merge(int[] arr, int l, int m, int r){
        int[] help = new int[r - l + 1];
        int i = help.length - 1;
        int p1 = m;
        int p2 = r;
        int res = 0;
        while(p1 >= l && p2 > m){
            res += arr[p1] > arr[p2] ? (p2 - m) : 0;
            //等于情况走右边
            help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
        }
        while(p1 >= l){
            help[i--] = arr[p1--];
        }
        while(p2 > m){
            help[i--] = arr[p2--];
        }
        //拷贝回原数组
        for (i = 0; i < help.length; i++) {
            arr[l+i] = help[i];
        }
        return res;
    }

    // for test
    public static int comparator(int[] arr) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    ans++;
                }
            }
        }
        return ans;
    }

    // for test
    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 * Math.random());
        }
        return arr;
    }

    // for test
    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;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (reversePairNum(arr1) != comparator(arr2)) {
                System.out.println("Oops!");
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println("测试结束");
    }
}

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138

2.3 翻转对

在一个数组中，对于每个数num，求有多少个后面的数*2 比如：[3,1,7,0,2]
3的后面有：1，0
1的后面有：0
7的后面有：0，2
0的后面没有
2的后面没有
所以总共有5个

关键思路：
依然是利用归并排序

int res = 0;
int windowR = m + 1;
for(int i = L; i <= m; i++){
	while(windowR <= r && (long)arr[i] > (long)arr[windowR]*2){
		windowR++;//继续向右边滑动，直到不大于为止
	}
	res += windowR - m - 1;
}
1
2
3
4
5
6
7
8

全部代码：

//归并排序解法：
class Solution {
    public int reversePairs(int[] nums) {
        if(nums == null || nums.length < 2){
            return 0;
        }
        return process(nums, 0, nums.length - 1);
    }
    
    public int process(int[] arr, int l, int r){
        if(l == r){
            return 0;
        }
        int m = l + ((r - l) >> 1);
        return process(arr, l, m) + process(arr, m+1, r) + merge(arr, l, m, r);
    }
    public int merge(int[] arr, int l, int m, int r){
        int[] help = new int[r - l + 1];
        int res = 0;
        //进行判断
        int windowR = m + 1;
        for(int i = l; i <= m; i++){
            while(windowR <= r && (long)arr[i] > (long)arr[windowR] * 2){
                windowR++;
            }
            res += windowR - m - 1;
        }
        int i = 0;
        int p1 = l;
        int p2 = m+1;
        while(p1 <= m && p2 <= r){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= m){
            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;
    }
}
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

2.4 区间和的个数

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        //前缀和数组
        long[] sum = new long[nums.length];
        sum[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            sum[i] = sum[i-1] + nums[i];
        }
        return process(sum, 0, sum.length - 1, lower, upper);
    }
    public int process(long[] sum, int l, int r, int lower, int upper){
        if(l == r){
            return sum[l] >= lower && sum[l] <= upper ? 1 : 0;
        }
        int m = l + ((r - l) >> 1);
        return process(sum, l, m, lower, upper) + process(sum, m + 1, r, lower, upper) 
            + merge(sum, l, m, r, lower, upper);
    }
    
    public int merge(long[] arr, int l, int m, int r, int lower, int upper){
        int ans = 0;
        int windowL = l;
        int windowR = l;
        for(int i = m + 1; i <= r; i++){
            long min = arr[i] - upper;
            long max = arr[i] - lower;
            while(windowR <= m && arr[windowR] <= max){
                windowR++;
            }
            //[)
            while(windowL <= m && arr[windowL] < min){
                windowL++;
            }
            ans += windowR - windowL;//sum是前缀和，因此这个减下来是个数
        }
        long[] help = new long[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m+1;
        while(p1 <= m && p2 <= r){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= m){
            help[i++] = arr[p1++];
        }
        while(p2 <= r){
            help[i++] = arr[p2++];
        }
        for(i = 0; i < help.length; i++){
            arr[l+i] = help[i];
        }
        return ans;
    }
}
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