Q1685-有序数组中差绝对值之和-中等-贪心

1685. 有序数组中差绝对值之和

Question

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

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

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

Example 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。

Example 2:

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

Note:

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= nums[i + 1] <= 10^4

Approach 1: 贪心

直接思路是在一层循环中遍历每个元素sum[i]，第二层循环计算它与其他元素差值的绝对值，并且求和。

class Solution:
    def getSumAbsoluteDifferences(self, nums):
        N = len(nums)
        ans=[]
        for i in range(N):
            dif = 0
            for j in range(N):
                if i != j:
                    dif += abs(nums[i] - nums[j])
            ans.append(dif)
        return ans

这样做的时间复杂度是O(n^2)，提示超出了时间限制，于是我们摄像能不能减少时间复杂度。

利用非递减数组的性质，可以提前计算前i项和 prefixSum[i] ，将后续的计算简化为：

对 sums[i] 左边的元素，单项差值为 ，前 i 项求和为

对 sums[i] 右边的元素，单项差值为 ，前 i 项求和为

class Solution:
    def getSumAbsoluteDifferences(self, nums):
        N = len(nums)
        sum = 0
        output = []
        prefixSum =[]
        for i in range(N):
            sum += nums[i]
            prefixSum.append(sum) # 前i项和
        for i in range(N):
            output.append((i+1)*nums[i]-prefixSum[i] + prefixSum[N-1]-prefixSum[i]-nums[i]*(N-1-i))
        return output

复杂度分析

• 时间复杂度：，N是序列长度。
• 空间复杂度：。常数个变量。