# 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;
}
~~~
