05、小和问题(JAVA，含对数器)--归并排序_java小和问题

题目描述

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

思路解析

其实可以直接用暴力循环的方式来做这道题，但这么做时间复杂度就会变成O(N²)，没技术含量不说，如果笔试的时候写这种算法那肯定是过不了，因此我们可以用换一种思路。

换个角度想，小和也可以这么算：假设数组中的一个元素a，右边有多少比a大的元素，就要加上多少个a，但是如果右边的元素比a小呢？那不又是一个O(N²)的算法吗？因此我们要保证一个前提，就是让a右边的元素有序排列。归并排序就可以很方便的帮我们解决这个问题。让我们根据归并排序的排序方式来逐步解析。

代码解析

1、分组

//归并排序--分组
	public static int process(int[] arr, int left, int right) {
		if (left == right) {
			// left==right，说明只剩一个数，则不存在小和，所以返回0
			return 0;
		}

		int mid = left + ((right - left) >> 1);//中间值的坐标
		return process(arr, left, mid)//分组
				+ process(arr, mid + 1, right)//分组
				+ merge(arr, left, mid, right);//归并
	}
1
2
3
4
5
6
7
8
9
10
11
12

2、比较

(1)、数组中只有一个元素

if (left == right) {
	// left==right，说明只剩一个数，则不存在小和，所以返回0
	return 0;
}
1
2
3
4

(2)、数组中有多个元素

int p = 0;//记录临时数组tmp的小标
int p1 = left;//记录左组第一个元素的下标
int p2 = mid + 1;//记录右组第一个元素的下标
int smallSum = 0;//记录当前数组的小和
1
2
3
4

//比较
while (p1 <= mid && p2 <= right) {
	smallSum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
     //计算当前数组的小和
}
1
2
3
4
5

计算小和的步骤

smallSum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;

• 从左组的第一个元素开始(arr[p1])，跟右组的第一个元素(arr[p2])进行比较：
• 如果arr[p1]小于arr[p2]，那就说明从arr[p2]开始(包括arr[p2])，右组的所有元素都大于arr[p1]，那么此时的小和就是arr[p1]乘上右组中大于arr[p1]的个数(right - p2 + 1)；
• 如果arr[p1]大于或等于arr[p2]，那就让右组的第二个元素跟arr[p1]进行比较，依次类推，当arr[p1]跟右组中的所有元素比较完后，再让左组的第二个元素跟右组的第一个元素比较，以此类推。

---

3、排序+归并

和归并排序的方法一样，如下所示：

int[] tmp = new int[(right - left) + 1];
//临时数组，用来存储已经排好序的元素，并将所有元素拷贝到当前数组中

while (p1 <= mid && p2 <= right) {
	smallSum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
     //求小和
	tmp[p++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
	//当左组中的元素(arr[p1])小于右组(arr[p2])时，
     //则将左组的元素(arr[p1)拷贝到tmp中；
     //当左组中的元素(arr[p1])大于或等于右组(arr[p2])时。
     //则将左组的元素(arr[p2)拷贝到tmp中
}

//将左组中的剩余元素存入tmp
while (p1 <= mid) {
	tmp[p++] = arr[p1++];
}

//将右组中的剩余元素存入tmp
while (p2 <= right) {
	tmp[p++] = arr[p2++];
}

//将tmp的内容拷贝到原数组中
for (int i = 0; i < tmp.length; i++) {
	arr[i+left]=tmp[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

举例

假设一个数组int[] arr={3,1,4,2,5};如果按照归并排序的方式递归分组，分完后就会是这样的情况：

从最底层开始：

对于数组⑧，其只有一个元素3，因此数组⑧的小和为0(只有一个数时，返回0)；
对于数组⑨，其只有一个数组1，因此数组⑨的小和为0(只有一个数时，返回0)；
1
2

然后将数组⑧和⑨进行排序，因为这两个数组都只有一个元素，故排序后不变，再将数组⑧和⑨进行归并后就是数组④的样子：

---

接着对数组④求小和，左组中第一个元素为3，右组中第一个元素为1，3大于1，因此数组④的小和为0。自此，数组④的小和已经求完了，接下来将数组④进行排序即可，排完后如下图：

因为第⑤组只有一个元素，因此其小和为0，而且也无需排序，然后将第④组和第⑤组合并：

接着按照计算小和的步骤依次进行，最后第②组的小和就为0+0+0+0+1×1+3×1=4(④⑤⑧⑨组的小和再加②组本身的小和)；

左半边排完了，右半边的步骤与其一样，因此右半边求完小和后的状态如下：

其小和为0+0+2×1=2(⑥⑦组的小和再加②组本身的小和)；

接着将②组和③组进行归并：

依旧根据计算小和的步骤，求得其小和为2+4+1×2+3×1+4×1=15

故最后的结果为15

---

完整代码

归并排序求小和：

package 苟熊岭熊哒;

//小和问题
public class SmallSum {
	// 归并排序求小和
	public static int smallSum(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}

		int left = 0;
		int right = arr.length - 1;
		int smallSum = process(arr, left, right);//分组
		return smallSum;
	}

	// 归并排序--分组
	public static int process(int[] arr, int left, int right) {
		if (left == right) {
			// left==right，说明只剩一个数，则不存在小和，所以返回0
			return 0;
		}

		int mid = left + ((right - left) >> 1);
		return process(arr, left, mid)
				+ process(arr, mid + 1, right)
				+ merge(arr, left, mid, right);
	}

	// 归并排序--归并
	public static int merge(int[] arr, int left, int mid, int right) {
		int[] tmp = new int[(right - left) + 1];
           int p = 0;//记录临时数组tmp的小标
           int p1 = left;//记录左组第一个元素的下标
           int p2 = mid + 1;//记录右组第一个元素的下标
           int smallSum = 0;//记录当前数组的小和

          //排序
		while (p1 <= mid && p2 <= right) {
			smallSum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
			tmp[p++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
			//只有当左组严格比右组小时，才将左组拷贝到tmp中
		}

		while (p1 <= mid) {
			tmp[p++] = arr[p1++];
		}

		while (p2 <= right) {
			tmp[p++] = arr[p2++];
		}

		for (int i = 0; i < tmp.length; i++) {
			arr[i+left]=tmp[i];
		}
		
		return smallSum;
		//返回小和
	}
	
	public static void main(String[] args) {
		int[] arr= {3,1,4,2,5};
		int result=smallSum(arr);//记录结果
		System.out.println(result);
	}
}
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

输出结果：

---

对数器测试

package 苟熊岭熊哒;

//小和问题
public class SmallSum {
	// 归并排序求小和
	public static int smallSum(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}

		int left = 0;
		int right = arr.length - 1;
		int smallSum = process(arr, left, right);//分组
		//System.out.println(smallSum);
		return smallSum;
	}

	// 归并排序--分组
	public static int process(int[] arr, int left, int right) {
		if (left == right) {
			// left==right，说明只剩一个数，则不存在小和，所以返回0
			return 0;
		}

		int mid = left + ((right - left) >> 1);
		return process(arr, left, mid)
				+ process(arr, mid + 1, right)
				+ merge(arr, left, mid, right);
	}

	// 归并排序--分组
	public static int merge(int[] arr, int left, int mid, int right) {
		int[] tmp = new int[(right - left) + 1];

		int p = 0;
		int p1 = left;
		int p2 = mid + 1;
		int smallSum = 0;//记录当前数组的小和

		while (p1 <= mid && p2 <= right) {
			smallSum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
			tmp[p++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
			//只有当左组严格比右组小时，才将左组拷贝到tmp中
		}

		while (p1 <= mid) {
			tmp[p++] = arr[p1++];
		}

		while (p2 <= right) {
			tmp[p++] = arr[p2++];
		}

		for (int i = 0; i < tmp.length; i++) {
			arr[i+left]=tmp[i];
		}
		
		return smallSum;
		//返回小和
	}
	
	//for test

	// 暴力循环求小和
	public static int comparator(int[] arr) {
		int smallSum = 0;// 小和
		if(arr==null||arr.length<2) {
			return 0;
		}

		// 从最后一个数开始，依次向前比较
		for (int i = arr.length - 1; i >= 0; i--) {
			int sum = 0;// 数组中每个数的小和
			for (int j = i - 1; j >= 0; j--) {
				if (arr[i] > arr[j]) {
					sum = sum + arr[j];
					//计算arr[i]处的小和
				}
			}
			smallSum += sum;
			//计算整个数组的小和
		}
		//System.out.println(smallSum);
		return smallSum;
	}
	
	// 生成一个随机数组
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		// Math.random() -> 随机在[0,1)范围内返回一个double类型的数(等概率)
		// Math.random()*A -> 随机在[0,A)范围内返回一个double类型的数(等概率)
		// (int)(Math.random()*A) -> 随机在[0,A-1]范围内返回一个int类型的数(等概率)
		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;
	}

	// 判断arr1和arr2中的每个值是否相等
	public static boolean isEqual(int result1, int result2) {
		return result1==result2;
	}

	// 打印数组
	public static void printArray(int result) {
		System.out.println(result);
	}

	public static void main(String[] args) {
		//对数器测试
		int testTime = 500000;// 测试次数，50万次
		int maxSize = 100;// 数组的规模不大于100
		int maxValue = 100;// 数组中每个值的范围，-100~+100
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			// 创建一个数组，长度随机，值也随机
			int[] arr2 = copyArray(arr1);
			// 拷贝arr1中的值和长度
			int result1= smallSum(arr1);//归并排序求小和
			int result2= comparator(arr2);//暴力方法求小和
			//比较result1和result2的结果
			if (isEqual(result1, result2) == false) {
				// 若值不一样，则该次测试失败
				succeed = false;
				printArray(result1);// 打印result1
				printArray(result2);// 打印result2
				break;// 跳出循环
			}
		}
		System.out.println(succeed ? "完全正确 !" : "有错误 !");
	}
}

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
141
142
143
144
145
146
147

输出结果：

---

这道题的介绍到这里就结束了，如果你觉得本篇文章对你多少有些帮助，可以点个赞或者收藏一波支持一下哦，欢迎各位大佬批评指正，咱们下次再见！