Skip to content

Latest commit

 

History

History

1685.Sum-of-Absolute-Differences-in-a-Sorted-Array

README.md

1685. Sum of Absolute Differences in a Sorted Array

题目

You are given an integer array nums sorted in non-decreasing order.

Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.

In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).

Example 1:

Input: nums = [2,3,5] Output: [4,3,5] Explanation: Assuming the arrays are 0-indexed, then 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:

Input: nums = [1,4,6,8,10] Output: [24,15,13,15,21]

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= nums[i + 1] <= 104

题目大意

给你一个 非递减 有序整数数组 nums 。请你建立并返回一个整数数组 result，它跟 nums 长度相同，且result[i] 等于 nums[i] 与数组中所有其他元素差的绝对值之和。换句话说， result[i] 等于 sum(|nums[i]-nums[j]|) ，其中 0 <= j < nums.length 且 j != i （下标从 0 开始）。

解题思路

  • 利用前缀和思路解题。题目中说明了是有序数组，所以在计算绝对值的时候可以拆开绝对值符号。假设要计算当前 result[i]，以 i 为界，把原数组 nums 分成了 3 段。nums[0 ~ i-1] 和 nums[i+1 ~ n]，前面一段 nums[0 ~ i-1] 中的每个元素都比 nums[i] 小，拆掉绝对值以后，sum(|nums[i]-nums[j]|) = nums[i] * i - prefixSum[0 ~ i-1]，后面一段 nums[i+1 ~ n] 中的每个元素都比 nums[i] 大，拆掉绝对值以后，sum(|nums[i]-nums[j]|) = prefixSum[i+1 ~ n] - nums[i] * (n - 1 - i)。特殊的情况，i = 0 和 i = n 的情况特殊处理一下就行。

代码

package leetcode //解法一 优化版 prefixSum + sufixSumfuncgetSumAbsoluteDifferences(nums []int) []int { size:=len(nums) sufixSum:=make([]int, size) sufixSum[size-1] =nums[size-1] fori:=size-2; i>=0; i-- { sufixSum[i] =sufixSum[i+1] +nums[i] } ans, preSum:=make([]int, size), 0fori:=0; i<size; i++ { // 后面可以加到的值res, sum:=0, sufixSum[i]-nums[i] res+= (sum- (size-i-1)*nums[i]) // 前面可以加到的值res+= (i*nums[i] -preSum) ans[i] =respreSum+=nums[i] } returnans } // 解法二 prefixSumfuncgetSumAbsoluteDifferences1(nums []int) []int { preSum, res, sum:= []int{}, []int{}, nums[0] preSum=append(preSum, nums[0]) fori:=1; i<len(nums); i++ { sum+=nums[i] preSum=append(preSum, sum) } fori:=0; i<len(nums); i++ { ifi==0 { res=append(res, preSum[len(nums)-1]-preSum[0]-nums[i]*(len(nums)-1)) } elseifi>0&&i<len(nums)-1 { res=append(res, preSum[len(nums)-1]-preSum[i]-preSum[i-1]+nums[i]*i-nums[i]*(len(nums)-1-i)) } else { res=append(res, nums[i]*len(nums)-preSum[len(nums)-1]) } } returnres }
close