Re: [閒聊] 每日LeetCode
我的思路是既然陣列中排序在後者一定不小於前者，
不妨將答案中的每個元素都視為後者減去前者的總和，
並且把跨越超過一個元素的差值都分解，
以第二個題目範例(nums=[1,4,6,8,10])來說，
如果定義a = nums[1] - nums[0]，
且b = nums[2] - nums[1]並以此類推，
則原題目會變成
result[0] = 4a + 3b + 2c + d = 24
result[1] = a + 3b + 2c + d = 15
result[2] = a + 2b + 2c + d = 13
result[3] = a + 2b + 3c + d = 15
result[4] = a + 2b + 3d + 4d = 21
可觀察到result[0]的值為每個差值乘以一個等差數列的總和，
並且result[1]相對於result[0]來說只少了3a的部分，
其他的答案之間也都是只變動一個元素，
所以就可以用O(n)的迴圈解決了
Python Code:
class Solution:
def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0 for i in range(n)]
ans[0] = sum([(nums[i] - nums[i-1]) * (n-i) for i in range(1,n)])
for i in range(1,n):
ans[i] = ans[i-1] - (nums[i] - nums[i-1]) * (n-i*2)
return ans
C++ Code:
class Solution {
public:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
const int n = nums.size();
vector<int> ans(n,0);
for (int i = 1;i < n;i++){
ans[0] += (nums[i] - nums[i-1]) * (n-i);}
for (int i = 1;i < n;i++){
ans[i] = ans[i-1] - (nums[i] - nums[i-1]) * (n-i*2);}
return ans;
}
};
※ 引述《ZooseWu (動物園 公告)》之銘言：
: 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), 來自: 1.161.104.149 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700890927.A.576.html
推
11/25 13:43,
2年前
, 1F
11/25 13:43, 1F
推
11/25 13:49,
2年前
, 2F
11/25 13:49, 2F
推
11/25 13:49,
2年前
, 3F
11/25 13:49, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 538 之 719 篇)：