有序数组中差绝对值之和

难度: Medium

给你一个 非递减 有序整数数组 nums 。

请你建立并返回一个整数数组 result，它跟 nums 长度相同，且result[i] 等于 nums[i] 与数组中所有其他元素差的绝对值之和。

换句话说， result[i] 等于 sum(|nums[i]-nums[j]|) ，其中 0 <= j < nums.length 且 j != i （下标从 0 开始）。

示例 1：

输入：nums = [2,3,5]
输出：[4,3,5]
解释：假设数组下标从 0 开始，那么
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4，
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3，
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。

示例 2：

输入：nums = [1,4,6,8,10]
输出：[24,15,13,15,21]

提示：

2 <= nums.length <= 10⁵
1 <= nums[i] <= nums[i + 1] <= 10⁴

Submission

运行时间: 84 ms

内存: 29.5 MB

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        x = nums[0]
        s = sum(nums) - x * n
        rst = [ s ]
        for i in range(1,n):
            d = nums[i] - x
            x = nums[i]
            s += (i * 2 - n) * d
            rst.append(s)
        return rst

Explain

本题解采用了前缀和的思想来优化计算每个result[i]的过程。初始时，计算result[0]时，我们可以直接使用一个简单的公式，即sum(nums) - nums[0] * n，这样可以直接得到nums[0]与所有其他元素的差的绝对值之和。接着，为了计算result[i]，我们不需要重新计算整个和，而是可以利用result[i-1]的结果。具体地，通过更新差值d = nums[i] - nums[i-1]，我们可以更新s的值。更新公式为：s += (i * 2 - n) * d，这个公式基于差分的思想，能够根据前一个元素的结果快速更新当前的结果。这种方法避免了对每个i重复计算总和，从而大大提高了效率。

时间复杂度: O(n)

空间复杂度: O(n)

# 定义一个解决方案

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)  # 数组长度
        x = nums[0]  # 初始元素，用于计算初值
        s = sum(nums) - x * n  # 计算初始s值，即result[0]
        rst = [s]  # 初始化结果列表，开始时只有第一个结果
        for i in range(1, n):
            d = nums[i] - x  # 计算当前元素与前一个元素的差
            x = nums[i]  # 更新当前元素
            s += (i * 2 - n) * d  # 使用差分更新s
            rst.append(s)  # 将新计算的结果添加到结果列表中
        return rst  # 返回最终结果列表

Explore

在已知result[i-1]的基础上计算result[i]的优化方法基于数学的递推关系。考虑数组中的每个元素与当前元素nums[i]的差的绝对值。当数组是有序的，我们知道前i个元素都小于等于nums[i]，而之后的元素都大于等于nums[i]。所以，从nums[i-1]到nums[i]的变化会使得对前i个元素的贡献增加i*d，而对后面的元素的贡献减少(n-i)*d。因此，总的变化量为(i*2-n)*d。这种通过递推式直接更新result[i]避免了重复计算，从而提高了算法效率。

更新公式`s += (i * 2 - n) * d`基于差分思想。当我们从nums[i-1]移动到nums[i]时，差值d = nums[i] - nums[i-1]。对于数组中前i个元素（小于等于nums[i]的元素），每增加1单位，差的绝对值增加的总和是i*d。对于剩余的n-i个元素，每增加1单位，差的绝对值减少的总和是(n-i)*d。因此，整体的变化量为i*d - (n-i)*d = (2*i-n)*d。这个公式精确地计算了从一个元素到下一个元素的变化，无需重新计算整个数组，从而实现了计算的优化。

在这个问题中，前缀和的概念略有扩展，不仅仅是累加，而是用于维护和更新每个元素对总和的贡献。初始时，我们计算了整个数组的和减去nums[0]乘以n的结果作为初始的result[0]。当数组中的元素从nums[i-1]更新为nums[i]时，我们利用已计算的result[i-1]和差值d来调整累计的总和，这类似于在前缀和的基础上进行动态的更新，而不是每次都从头开始计算，这样大大减少了重复计算，提高了效率。

数组`nums`中的相同元素不会影响这种方法的适用性。在计算过程中，相同元素意味着在这些元素之间的差值d将会是0，因此更新公式`s += (i * 2 - n) * d`中的d为0，s的值不会因这部分元素而发生变化。这反映了一个事实：当元素相同时，它们对于差的绝对值之和的贡献是不变的。因此，这种情况下算法仍然是有效的，不会因为元素的重复而失效。