小和问题 在一个数组中， 每一个数左边比当前数小的数累加起来， 叫做这个数组的小和。 求一个数组 的小和。 例子： [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
如果直接用两层for循环扫一遍，时间复杂度O(n*n)，这个题目可以利用归并排序把时间复杂度降到O(nlogn)
上代码
代码语言：javascript复制import java.io.BufferedInputStream;
import java.util.Scanner;
public class test {
public static int[] help;
public static int mergeSort(int[] a) {
if (a == null || a.length < 2) {
return 0;
}
help = new int[a.length];
return sort(a, 0, a.length - 1);
}
public static int sort(int[] a, int lo, int hi) {
if (lo >= hi) {
return 0;
}
int mid = lo ((hi - lo) >> 1);
return sort(a, lo, mid) sort(a, mid 1, hi) merge(a, lo, mid, hi); // 回到大区间的时候每部分都排好序了
}
public static int merge(int[] a, int lo, int mid, int hi) {
int j = lo, k = mid 1, res = 0;
for (int i = lo; i <= hi; i) {
help[i] = a[i];
}
for (int i = lo; i <= hi; i) {
if (j > mid) {
a[i] = help[k ];
} else if (k > hi) {
a[i] = help[j ];
} else if (help[j] < help[k]) {
res = (hi - k 1) * help[j]; // k~hi之间的所有数都比help[j]大， res就是对help[j]来说前面小于它的数字之和
a[i] = help[j ];
} else {
a[i] = help[k ];
}
}
return res;
}
public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int n = cin.nextInt(); // 要排序的数量
int[] a = new int[n]; // 如果要排字符串用String[]，排double用Double[]，以此类推，就成了通用排序数组
for (int i = 0; i < n; i) {
a[i] = cin.nextInt();
}
cin.close();
System.out.println(mergeSort(a)); // 在排好序的时候小数和已经求出来了
/*if (n != 0) {
System.out.print(a[0]);
}
for (int i = 1; i < n; i) {
System.out.print(" " a[i]);
}*/
}
}
