LeetCode 补充题 8. 计算数组的小和

Categories:

题目描述
思路分析
1. 解法一：归并排序统计小和（推荐）
相似题目

题目描述

✅ 补充题 8. 计算数组的小和

思路分析

解法一：归并排序统计小和（推荐）

核心思路：

小和定义为：对每个位置 i，累加其左侧所有小于 arr[i] 的元素值。

在归并排序合并阶段，若左侧元素 arr[i] < arr[j]，则它会对右侧剩余元素产生贡献。

贡献值为 arr[i] * (rightEnd - j + 1)。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，归并排序辅助数组占用线性空间。

class Solution {
    public int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + (r - l) / 2;
        int left = process(arr, l, mid);
        int right = process(arr, mid + 1, r);
        int merge = merge(arr, l, mid, r);
        return left + right + merge;
    }

    private int merge(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int i = l;
        int j = m + 1;
        int idx = 0;
        int sum = 0;

        // 归并过程中统计小和
        while (i <= m && j <= r) {
            if (arr[i] < arr[j]) {
                sum += arr[i] * (r - j + 1);
                help[idx++] = arr[i++];
            } else {
                help[idx++] = arr[j++];
            }
        }

        while (i <= m) {
            help[idx++] = arr[i++];
        }
        while (j <= r) {
            help[idx++] = arr[j++];
        }

        System.arraycopy(help, 0, arr, l, help.length);
        return sum;
    }
}

func smallSum(arr []int) int {
	if len(arr) < 2 {
		return 0
	}
	return process(arr, 0, len(arr)-1)
}

func process(arr []int, l int, r int) int {
	if l == r {
		return 0
	}
	mid := l + (r-l)/2
	left := process(arr, l, mid)
	right := process(arr, mid+1, r)
	merge := merge(arr, l, mid, r)
	return left + right + merge
}

func merge(arr []int, l int, m int, r int) int {
	help := make([]int, r-l+1)
	i, j, idx := l, m+1, 0
	sum := 0

	// 归并过程中统计小和
	for i <= m && j <= r {
		if arr[i] < arr[j] {
			sum += arr[i] * (r - j + 1)
			help[idx] = arr[i]
			i++
		} else {
			help[idx] = arr[j]
			j++
		}
		idx++
	}

	for i <= m {
		help[idx] = arr[i]
		idx++
		i++
	}
	for j <= r {
		help[idx] = arr[j]
		idx++
		j++
	}

	copy(arr[l:r+1], help)
	return sum
}

相似题目

题目	难度	考察点
315. 计算右侧小于当前元素的个数	困难	归并排序
327. 区间和的个数	困难	归并排序
493. 翻转对	困难	归并排序
912. 排序数组	中等	归并排序
164. 最大间距	困难	排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/43494579