class Solution {
public:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
}
};
1685. 有序数组中差绝对值之和
给你一个 非递减 有序整数数组 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 <= 1051 <= nums[i] <= nums[i + 1] <= 104原站题解
golang 解法, 执行用时: 120 ms, 内存消耗: 9 MB, 提交时间: 2022-11-28 13:59:11
func getSumAbsoluteDifferences(nums []int) []int {
res := make([]int, 0)
r := 0
for i:=1; i < len(nums); i++{
r+=nums[i]
}
l := 0
length := len(nums)-1
for i:=0; i < len(nums); i++{
if i!=0{
r -= nums[i]
}
res = append(res, ((i-0) * nums[i]-l) + r - (length-i)*nums[i] )
l += nums[i]
}
return res
}
java 解法, 执行用时: 3 ms, 内存消耗: 54 MB, 提交时间: 2022-11-28 13:58:05
class Solution {
public int[] getSumAbsoluteDifferences(int[] nums) {
int sum = 0;
int[] prefixSum = new int[nums.length];
//计算前缀和
for(int i=0;i<nums.length;i++){
sum += nums[i];
prefixSum[i] = sum;
}
//计算每个数的差绝对值之和
int[] output = new int[nums.length];
for(int i=0;i<nums.length;i++){
// int sumOfLeftDifferences = (i+1)*nums[i]-prefixSum[i];
// int sumOfRightDifferences = prefixSum[nums.length-1]-prefixSum[i]-nums[i]*(nums.length-1-i);
// sumOfDifferences = sumOfLeftDifferences+sumOfRightDifferences;
output[i] = (i+1)*nums[i]-prefixSum[i]+ prefixSum[nums.length-1]-prefixSum[i]-nums[i]*(nums.length-1-i);
}
return output;
}
}
python3 解法, 执行用时: 136 ms, 内存消耗: 27.2 MB, 提交时间: 2022-11-28 13:57:32
class Solution:
def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
ans[0] = sum(nums) - nums[0] * n
for i in range(1, n):
d = nums[i] - nums[i - 1]
ans[i] = ans[i - 1] - (n - i * 2) * d
return ans
python3 解法, 执行用时: 184 ms, 内存消耗: 27.3 MB, 提交时间: 2022-11-28 13:55:33
class Solution:
def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
for i in range(n):
res[0] += (nums[i] - nums[0])
for i in range(1, n):
res[i] = res[i-1] + (nums[i] - nums[i-1]) * (2*i - n)
return res