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小的数没有
- 第二个元素2：前面比2小的数小和为1
- 第三个元素3：前面比3小的数小和为1 + 2 = 3
- 第四个元素2：前面比2小的数小和为1
- 第五个元素5：前面比5小的数小和为1 + 2 + 3 + 2 = 8
- 所以数组小和为上述五个步骤的累加和为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 分析
- 采用归并排序算法，时间复杂度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)
