欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

左神算法 计算数组小和

程序员文章站 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;
    }


}