活用軸心點觀念 Sum of Absolute Diff in Sorted Array_Leetcode #1685

Chun Kit Soo on Unsplash

題目敘述

題目會給我們一個陣列nums，要求我們以每個陣列元素分別當作軸心點，計算差值的絕對值總和，最後以陣列的形式，返回答案。

測試範例

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[i]而言

題目所求

= abs( nums[i] - nums[0] ) + abs( nums[i] - nums[1] ) + ... + abs( nums[i] - nums[i-1] ) + abs( nums[i] - nums[i+1] ) + ... + abs( nums[i] - nums[n-1] )

= num[i] 對比較小的那一群數字的差值絕對值總和 +

num[i] 對比較大的那一群數字的差值絕對值總和

= abs { nums[i] * i - sum of smaller numbers } +

abs{ nums[i] * (n-1-i) - sum of larger numbers }

= nums[i] * i - sum of smaller numbers +

sum of larger numbers - nums[i] * (n-1-i)

我們可以用一個線性掃描，從左往右，每次迭代更新 比較小的那一群數字總和、比較大的那一群數字總和，計算整體的差值絕對值總和。

最終，以陣列的形式返回答案即可。

程式碼

class Solution:
　def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
　　
　　n = len(nums)
　　sum_below, sum_above = 0, sum(nums)

　　sum_abs_diff = []

　　# Iterate each number
　　for i, number in enumerate(nums):
　　　
　　　# Sum of numbers smaller than nums[i]
　　　sum_below += number

　　　# Sum of absolute difference to smaller numbers
　　　diff_sum_below = i * number - sum_below

　　　# Sum of absolute difference to larger numbers
　　　diff_sum_above = sum_above - (n-1-i) * number

　　　sum_abs_diff.append( diff_sum_below + diff_sum_above )

　　　# Sum of numbers larger than nums[i]
　　　sum_above -= number

　　return sum_abs_diff 

複雜度分析

時間複雜度: O(n)

線性掃描，從左到右掃描每個陣列元素，總共耗時O(n)

空間複雜度: O(1)

解答所使用的空間sum_abs_diff不包含在內。
剩下的都是固定尺存的臨時變數，為常數級別O(1)

關鍵知識點

從圖解，和歸納小規模的例子可以發現:

我們可以用一個線性掃描，從左往右，每次迭代更新 比較小的那一群數字總和、比較大的那一群數字總和，計算整體的差值絕對值總和。

Reference:

[1] Python O(n) by linear scan [w/ Visualization] - Sum of Absolute Differences in a Sorted Array - LeetCode