2023-11-25|閱讀時間 ‧ 約 5 分鐘

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

題目敘述

題目會給我們一個陣列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

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.