# 1. 小和问题
在一个数组中，每一个数左边比当前数小的数累加起来的求和。比如：`arr=[1, 3, 4, 2, 5]`
- 对于`1`，左边没有比它小的数，为`0`；
- 对于`3`左边比它小的数为`1`；
- 对于`4`左边比它小的数为`1`和`3`；
- 对于`2`左边比它小的数为`1`；
- 对于`5`左边比它小的数为`1`、`3`、`4`、`2`。
所以其小和为`1+1+3+1+1+3+4+2 = 16`
对于这个问题，我们很容易可以写出一个`O(n^2)`时间复杂度的算法，但是没有多少意义。比如下面的代码：
~~~
public int getMinSum(int[] arr){
int len = 0, res = 0;
if(arr == null || (len = arr.length) == 0) return res;
for (int i = 0; i < len; i++) {
int count = 0;
for (int j = 0; j < i; j++) {
if(arr[i] > arr[j]){
count += arr[j];
}
}
res += count;
}
return res;
}
~~~
可以等价进行转换。转换为求某个数的右边比它大的数，同理：
- 对于`1`，右边四个数都比它大，所以为`4*1=4`;
- 对于`3`右边两个数比它大，所以为`3*2=6`;
- 对于`4`右边一个数比它大，所以为`1*4=4`;
- 对于`2`右边一个数比它大，所以为`1*2=2`；
- 对于`5`右边没有比它大的，为`0`；
所以其小和为：`4+6+4+2=16`
类似的，也可以很直观的写出当前的算法逻辑：
~~~
public int getMinSum(int[] arr){
int len = 0, res = 0;
if(arr == null || (len = arr.length) == 0) return res;
for (int i = 0; i < len - 1; i++) {
int count = 0;
for (int j = i + 1; j < len; j++) {
if(arr[i] < arr[j]){
count++;
}
}
res += (count * arr[i]);
}
return res;
}
~~~
但其实这种方式和上面的没有多少区别。时间复杂度上还是等价的。其实，对于上面的转化可以用**归并排序来进行拓展求解**。
我们知道归并排序的基本思路为划分子问题然后递归的求解。那么我们如果需要使用归并的思路来解决这个问题，就需要思考在最小的子问题的地方应该如何计算当前数的右边有多少个比它大的数。那么在归并的过程中可以进行统计计算，如下图所示：
那么代码为：
~~~
public int getMinSum(int[] arr) {
if (arr == null || arr.length == 0) return 0;
return twoWayMergeSort(arr, 0, arr.length - 1);
}
private int twoWayMergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + ((right - left) >> 1);
return twoWayMergeSort(arr, left, mid)
+ twoWayMergeSort(arr, mid + 1, right)
+ merge(arr, left, mid, right);
} else return 0;
}
private int merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int index = 0;
int p = low, q = mid + 1;
int result = 0;
while (p <= mid && q <= high) {
if (arr[p] > arr[q]) {
temp[index++] = arr[q++];
} else {
result += arr[p] * (high - q + 1);
temp[index++] = arr[p++];
}
}
while (p <= mid) {
temp[index++] = arr[p++];
}
while (q <= high) {
temp[index++] = arr[q++];
}
for (int i = 0; i < temp.length; i++) {
arr[low + i] = temp[i];
}
return result;
}
~~~
