解題區►Leetcode►Medium

Leetcode 1685 - Sum of Absolute Differences in a Sorted Array

題目

Problem#

給你一個遞減排序的整數陣列 nums ，要你回傳另一個整數陣列 result[i] 代表 nums[i] 與 nums 裡的所有數字的差距的絕對值總和。
result[i] = sum(|nums[i]-nums[j]|) where 0 <= j < nums.length && j != i

測資限制#

  • $2 \le n \le 10^5$
  • $1 \le \text{nums}[i] \le \text{nums}[i+1] \le 10^4$

想法#

觀察一下規律，例如 nums = [a, b, c, d, e]，應該可以發現對於 result[i] 其中 nums[i] 都有一項是會和自己相減 = 0，左邊的數字 (0 ~ i-1) 都是 nums[i] - nums[j]；右邊的數字都是 nums[j] - nums[i]，因為大減小才是正數

1
2
3
4
5
6
7
     nums =  [0]     [1]     [2]     [3]    [4]
------------------------------------------------
result[0] = (a-a) +  b-a  +  c-a  +  d-a  +  e-a
result[1] =  b-a  + (b-b) +  c-b  +  d-b  +  e-b
result[2] =  c-a  +  c-b  + (c-c) +  d-c  +  e-c
result[3] =  d-a  +  d-b  +  d-c  + (d-d) +  e-d
result[4] =  e-a  +  e-b  +  e-c  +  e-d  + (e-e)

以 result[2] 為例:
左邊是 $(c-a) + (c-b) + (c-c) = c \times 3 - (a + b + c)$
右邊是 $(c-c) + (d-c) + (e-c) = (c + d + e) - c \times 3$

result[i] = 左邊的數字總和 + 右邊的數字總和，其中:

  • 左邊的數字總和 = $(\text{nums}[i]\times(i+1)) - (\text{nums}[0]+\text{nums}[1]+…+\text{nums}[i])$
  • 右邊的數字總和 = $(\text{nums}[i]+\text{nums}[i+1]+…+\text{nums}[n-1]) - (\text{nums}[i]\times(n-i))$

AC Code#

  • 時間複雜度: $\mathcal{O}(n)$
  • 空間複雜度: $\mathcal{O}(n)$