左神算法 计算数组小和
程序员文章站
2024-03-15 22:26:21
...
给定数组,对于每个值来说,它左边的小于等于它的数之和称为小和,返回整个数组的小和之和。
这里换个思路,数组分一半,求出左边的某个值比右半数组多少个数小,这是数组间的小和累加,再求左半边数组和右半边数组的小和,相当于将问题的规模减小了。
归并排序的思想
下面的是代码:
public class Main {
public static void main(String[] args) {
int[] arr = { 3, 1, 2, 4, 6, 2, 7, 8, 1, 7,9,0,4,5,6,7,8,2};
int[] tmp = new int[arr.length];
System.out.println(getSmallSum(arr, 0, arr.length -1, tmp));
}
public static int getSmallSum(int[] arr, int start, int end, int[] tmp){
if (start >= end){
return 0;
}
int mid = (end-start)/2 + start;
int res1 = getSmallSum(arr, start, mid, tmp);
int res2 = getSmallSum(arr, mid +1 , end, tmp);
int res3 = merge(arr, start, mid, end, tmp);
return res1 + res2 + res3;
}
public static int merge(int[] arr, int start, int mid, int end, int[] tmp){
int res = 0;
int left = start, right = mid +1;
int index = left;
while (left <= mid && right <= end){
if (arr[left] <= arr[right]){
res += (end-right+1) * arr[left];
tmp[index] = arr[left];
++left;
}
else {
tmp[index] = arr[right];
++right;
}
index++;
}
while (left <= mid){
tmp[index] = arr[left];
++index;
++left;
}
while (right <= end){
tmp[index] = arr[right];
++index;
++right;
}
for (int i = start; i <= end; i++) {
arr[i] = tmp[i];
}
return res;
}
}
下一篇: 左神算法:加强堆的实现(Java)