问题描述
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子 [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
这个例子总是看不明白，为什么呢？因为分治思想在这里体现的时候，会误导新手；这个例子很巧的，分治之后，都是左边小于右边的，如图： 说巧不巧，人家就是有顺序的！，左边从小到大，右边从小到大，都是先天的有序！1<3<4，2<5。所以为了更好的理解这个分治的思想，我们换个例子，把例子修改一下，变成这样：
稍作修改
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子 [4,3,1,5,2] 4左边比4小的数：没有 3左边比3小的数：没有 1左边比1小的数：没有 5左边比5小的数：4，3，1 2左边比2小的数：1 所以小和为4+3+1+1=9
现在我们开始来用分治的思想来做这个题，就变成了这个样子：
这个修改的例子里面，就能体现出来，每一次的比对，结果都利用上了；4和3比较，没有人比4小，但是我们得到了大小信息，把顺序保存在help里面，4，3和1比较，同样没有人比1小，但是，比较 的信息我们保存在了help里面…
代码
public class Main {
public static void main(String
[] args
) {
int arr
[] = {4,3,1,5,2};
System
.out
.println("sum is : "+smallSum(arr
));
}
public static int smallSum(int[] arr
) {
if (arr
== null
|| arr
.length
< 2) {
return 0;
}
return mergeSort(arr
, 0, arr
.length
- 1);
}
public static int mergeSort(int[] arr
, int l
, int r
) {
if (l
== r
) {
return 0;
}
int mid
= l
+ ((r
- l
) >> 1);
return mergeSort(arr
, l
, mid
) + mergeSort(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
) {
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
];
System
.out
.println(help
[i
]);
}
System
.out
.println("help end !");
return res
;
}
}
结果：
