Re: [閒聊] 每日LeetCode
1685. Sum of Absolute Differences in a Sorted Array
給你一個從小排到大的正整數陣列
回傳新的陣列包含以下特性：
每個元素都是原本陣列減其他元素後取絕對值的總和
Input: nums = [2,3,5]
Output: [4,3,5]
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.
Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]
Intuition:
把陣列列出來之後整理就能得到算法。
Approach:
我們把例題[2,3,5]的算法列出來並展開絕對值：
result[0] = |2-2| + |2-3| + |2-5| = 2-2 + 3-2 + 5-2
result[1] = |3-2| + |3-3| + |3-5| = 3-2 + 3-3 + 5-3
result[2] = |5-2| + |5-3| + |5-5| = 5-2 + 5-3 + 5-5
把計算重新整理
依陣列元素與自己分成兩邊：
2-2 + 3-2 + 5-2 = ( 2+3+5) - (2+2+2)
3-2 + 3-3 + 5-3 = (-2+3+5) - (3+3-3)
5-2 + 5-3 + 5-5 = (-2-3+5) - (5-5-5)
這樣我們就能看出規律
變化分成兩個部分：
1.左半邊:初始是總和 每次會減少前一個計算的元素的兩倍
2.右半邊:初始是元素數量 每次會-2
( 2+3+5) - (2+2+2) = (( 2+3+5)) - 2* 3
(-2+3+5) - (3+3-3) = (( 2+3+5)-2*2) - 3* 1
(-2-3+5) - (5-5-5) = ((-2+3+5)-3*2) - 5*(-1)
根據上面找到的規律去計算就是答案
題目已經排序過輸入進來的陣列
所以直接跑迴圈就好
TS Code:
function getSumAbsoluteDifferences (nums: number[]): number[] {
let result: number[] = []
let absSum = nums.reduce((p, c) => p + c, 0)
let elementCount = nums.length
for (let i = 0; i < nums.length; i++) {
const element = nums[i]
result.push(absSum - element * elementCount)
elementCount -= 2
absSum -= element * 2
}
return result
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700884562.A.1FF.html
推
11/25 11:58,
2年前
, 1F
11/25 11:58, 1F
推
11/25 12:05,
2年前
, 2F
11/25 12:05, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 537 之 719 篇)：