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]，因為大減小才是正數

     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#

Copy

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& v)
    {
        vector<int> ans;
        int n = v.size();
 
        // prefix sum
        vector<int> pre(n);
        for(int i = 0; i < n; i++)
            pre[i] = (i >= 1 ? pre[i-1]+v[i] : v[i]);
        // sum(a, b) = v[a]+...+v[b]
        auto sum = [&](int a, int b) {
            return pre[b] - (a-1 >= 0 ? pre[a-1] : 0);
        };
 
        for(int i = 0; i < n; i++)
        {
            int tmp = 0;
            tmp += v[i]*(i+1) - sum(0, i);
            tmp += sum(i, n-1) - (v[i]*(n-i));
            ans.push_back(tmp);
        }
 
        return ans;
    }
};

view raw leetcode/1685.cpp delivered with ❤ by emgithub

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