关于算法:归并排序的扩展问题

归并排序的扩大：（左神算法笔记）

小和问题

在一组数组中，每一个数右边比以后数小的数累加起来，叫作这个数组的小和。求一个数组的小和。
例子：[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.

public class SmallSum {static int smallSum(int[] arr) {if (arr == null || arr.length < 2) return 0;
        return process(arr, 0, arr.length - 1);
    }
    // 在 arr[left,right] 上既要排好序，又要求小和
    private static int process(int[] arr, int left, int right) {if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        return process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, mid, right);
    }

    private static int merge(int[] arr, int left, int mid, int right) {int[] help = new int[right - left + 1];
        int i = 0, a = left, b = mid + 1;
        int res = 0;
        while (a <= mid && b <= right) {if (arr[a] < arr[b]) res += (right - b + 1) * arr[a];
            help[i++] = arr[a] < arr[b] ? arr[a++] : arr[b++];
        }
        while (b <= right) {help[i++] = arr[b++];
        }
        while (a <= mid) {help[i++] = arr[a++];
        }
        for (i = 0; i < help.length; i++) {arr[left + i] = help[i];
        }
        return res;
    }

    public static void main(String[] args) {int[] arr = {1, 3, 4, 2, 5};
        System.out.println(smallSum(arr));
    }
}

逆序对问题

在一个数组中，右边的数如果比左边的数大，则这两个数形成一个逆序对，输入数组中逆序对的总个数。

• https://leetcode-cn.com/probl…

public class ReversePair {public static int reversePairs(int[] arr) {if (arr == null || arr.length < 2) return 0;
        int[] copy = new int[arr.length];
        for (int i = 0; i < arr.length; i++) copy[i] = arr[i];
        return reversePairs(copy, 0, arr.length - 1);
    }

    // arr[left, right] 计算逆序对个数并排序
    private static int reversePairs(int[] arr, int left, int right) {if (left == right) return 0;
        int mid = left + (right - left) / 2;
        int leftCount = reversePairs(arr, left, mid);
        int rightCount = reversePairs(arr, mid + 1, right);
        int mergeCount = merge(arr, left, mid, right);
        return leftCount + rightCount + mergeCount;
    }

    private static int merge(int[] arr, int left, int mid, int right) {
        int i = 0, a = left, b = mid + 1;
        int[] help = new int[right - left + 1];
        int res = 0;
        while (a <= mid && b <= right) {if (arr[a] > arr[b]) res += mid - a + 1;
            help[i++] = arr[b] < arr[a] ? arr[b++] : arr[a++];
        }
        while (a <= mid) {help[i++] = arr[a++];
        }
        while (b <= right) {help[i++] = arr[b++];
        }
        for (i = 0; i < help.length; i++) {arr[left + i] = help[i];
        }
        return res;
    }
}

两个问题的外围点都是在 merge 的过程中计算出须要的后果。