算法001. 数组小和

1. 题目描述

在一个数组 nums 中，对于第 i 个数 nums[i], 将 i 左边所有比 nums[i] 小的数累加所得的值 sum, 叫做数组 nums[i] 的小和。将数组所有位置的小和累加起来所得的值叫做数组的小和。
给定数组 nums, 请输出数组 nums 的小和。

【举例】

• 输入 [1, 2, 3, 2, 5]
• 输出 1 + 1 + 2 + 1 + 1 + 2 + 3 + 2 = 13
• 解释
  1. 第一个元素1：前面比1小的数没有
  2. 第二个元素2：前面比2小的数小和为1
  3. 第三个元素3：前面比3小的数小和为1 + 2 = 3
  4. 第四个元素2：前面比2小的数小和为1
  5. 第五个元素5：前面比5小的数小和为1 + 2 + 3 + 2 = 8
  6. 所以数组小和为上述五个步骤的累加和为13

2. 解题思路

1. 暴力求解

两层 for 循环，分析过程略，代码如下

    public static int forceSmallSum(int[] nums) {
        if(nums == null || nums.length <= 1) {
            return 0;
        }
        int result = 0;
        for(int i=1; i<nums.length; i++) {
            for(int j=0; j<i; j++) {
                if(nums[j] < nums[i]) {
                    result += nums[j];
                }
            }
        }
        return result;
    }

很显然，时间复杂度 O(n), 空间复杂度 O(1).

2. 归并排序求解

2.1 分析

2. 采用归并排序算法，时间复杂度O(N logN), 空间复杂度O(NlogN)

• 规定：当左右分组merge时，只有当左侧的数比右侧数小时，才将左侧数字作为小和进行加和
• 解释：可以将次题目看作是对每个元素num[i]寻找其后面有几个元素比num[i]大

2.2 代码如下

    // 求数组 nums 小和
    public static int mergeSmallSum(int[] nums) {
        if(nums == null || nums.length < 1) {
            return 0;
        }
        return mergeSortSmallSum(nums, 0, nums.length - 1);
    }

    // 求出从 start ~ end 归并排序过程中所产生的小和
    private static int mergeSortSmallSum(int[] nums, int start, int end) {
        if(start == end) {
            return 0;
        }
        int mid = start + ((end - start) >> 1);
        // 左边部分的小和
        int leftSmallSum = mergeSortSmallSum(nums, start, mid);
        // 右边部分的小和
        int rightSmallSum = mergeSortSmallSum(nums, mid + 1, end);
        // 合并过程中产生的小和
        int mergeProcessSmallSum = merge(nums, start, mid, end);
        // 返回小和的累加
        return leftSmallSum + rightSmallSum + mergeProcessSmallSum;
    }

    // 合并start ~ mid、mid+1 ~ end 的元素使其有序，并返回合并过程中产生的小和
    private static int merge(int[] nums, int start, int mid, int end) {
        int[] help = new int[end - start + 1];
        int helpIndex = 0;
        int left = start;
        int right = mid + 1;
        int result = 0;
        while(left <= mid && right <= end) {
            if(nums[left] < nums[right]) {
                // 如果左侧小，而右侧已经是排过序的，则说明右侧比左侧大的数有 （end - right + 1）个
                result += (end - right + 1) * nums[left];
                help[helpIndex++] = nums[left++];
            } else {
                help[helpIndex++] = nums[right++];
            }
        }
        while(left <= mid) {
            help[helpIndex++] = nums[left++];
        }
        while (right <= end) {
            help[helpIndex++] = nums[right++];
        }
        for(int i=start, j=0; i<=end; i++, j++) {
            nums[i] = help[j];
        }
        return result;
    }

时间复杂度和归并排序的时间复杂度相同 O(nlogn), 空间复杂度也和鬼并排序相同 O(nlogn)