526互联

[LeetCode] 1685. Sum of Absolute Differences in a Sorted Array

发布时间 2023-11-30 01:56:43作者: CNoodle

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 开始）。

思路

我参考了这个帖子。注意题目给的 input 是一个非递减的数组，那么对于任何一个数字 nums[i] 而言，位于他左边的数字的累加和就很容易通过前缀和的方式计算出来，同理，位于 nums[i] 右边的数字也可以被求出来。那么当我们用 O(n) 的时间求出整个 input 数组的前缀和之后，我们就可以用 O(1) 的时间来求出每个位置上的数字与其他数字的差的绝对值之和。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
		int[] res = new int[n];
		int[] presum = new int[n + 1];
		for (int i = 0; i < n; i++) {
			presum[i + 1] = presum[i] + nums[i];
		}

		for (int i = 0; i < n; i++) {
			res[i] = i * nums[i] - presum[i] + (presum[n] - presum[i] - (n - i) * nums[i]);
		}
		return res;
    }
}