LeetCode 1685 Sum of Absolute Differences in a Sorted Array

題目連結

❗️ 題意

• 給定一個 Non-decreasing的陣列 $nums$, 請輸出一個與原本的 nums大小相同的陣列 $results$，對於$results[i]$，其值為$nums[i]$與其他所有元素$nums[j]$的絕對值總和，如範例所示。
  • Input: $[2,3,5]$
  • Output: $[4,3,5]$
    • $4 = |2 - 3| + |2 - 5|$
    • $3 = |3 - 2| + |3 - 5|$
    • $5 = |5 - 2| + |5 - 3|$
  • Constraints:
    • $2 \leq nums.length \leq 10^5$
    • $1 \leq nums[i] \leq nums[i + 1] \leq 10^4$

---

✔️ 題解

首先，這題我們可以先想到暴力解的方式，利用兩個迴圈窮舉任兩個元素之間的絕對值再累加出答案，此種方式的時間複雜度為$O(n^2)$，對於nums的長度為$10^5$而言顯然一定會吃一個TLE。
因此，我們就需要利用到nums這個陣列是「已排序」的條件來解決此題目，首先我們可以觀察到一個情況，對於某個$nums[i]$來說，$num[0] \sim nums[i - 1]$都會比$nums[i]$小，相反地，對於$nums[i + 1] \sim nums[nums.length - 1]$一定都比$nums[i]$來得大，透過利用此特性，我們就可以先將$num[0] \sim nums[i - 1]$與$nums[i + 1] \sim nums[nums.length - 1]$的部分先計算出來，而答案就是比$nums[i]$還小的數值的總和減掉與其相同數量($i - 1$個)的$nums[i]$，再去加上比$nums[i]$還大的數值總和掉相同數量($nums.length - 1 - i$個)的$nums[i]$。
而如何快速的計算區間的總和也是一個問題，在這部分，我們可以透過前綴和(Prefix Sum)的方式，宣告一個新的陣列$prefix$，其中$prefix[i]$內存的就是$nums[0] \sim nums[i]$的總和，以此我們就能夠快速的知道比某個$nums[i]$還小的總和與比$nums[i]$還大的總和，分別為$prefix[i - 1]$與$prefix[nums.length - 1] - prefix[i]$，而對於最後的答案，我們可以分別計算兩者結果，再將其總和，以下面表示：

• $lesser = nums[i] * i - prefix[i - 1]$
• $greater = (prefix[n - 1] - prefix[i]) - (n - 1 - i) * nums[i]$
• $ans = lesser + greater$

---

💻 程式碼

// TLE
class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<int>ans(n, 0);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                ans[i] += abs(nums[i] - nums[j]);
            }
        }
        return ans;
    }
};

// 70ms, AC
class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        int prefix[n];
        memset(prefix, 0, sizeof(prefix));
        prefix[0] = nums[0];
        for(int i = 1; i < n; i++){
            prefix[i] = prefix[i - 1] + nums[i];
        }
        vector<int>result;
        result.emplace_back(prefix[n - 1] - prefix[0] - (n - 1) * prefix[0]);
        for(int i = 1; i < n; i++){
            int lesser = nums[i] * i - prefix[i - 1];
            int greater = (prefix[n - 1] - prefix[i]) - (n - 1 - i) * nums[i];
            result.emplace_back(lesser + greater);
        }
        return result;
    }
};

Runtime: 70 ms, faster than 99.11% of C++ online submissions

---

🧠 心得

最近開始佛系刷LeetCode，一天大概寫3~5題左右，以後遇到有趣的題目再放上來與大家分享我的解題方法與心得啦～

---