{"id":7790,"date":"2020-12-12T16:48:31","date_gmt":"2020-12-13T00:48:31","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7790"},"modified":"2020-12-12T17:12:27","modified_gmt":"2020-12-13T01:12:27","slug":"leetcode-1685-sum-of-absolute-differences-in-a-sorted-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-1685-sum-of-absolute-differences-in-a-sorted-array\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1685. Sum of Absolute Differences in a Sorted Array"},"content":{"rendered":"\n

You are given an integer array nums<\/code> sorted in non-decreasing<\/strong> order.<\/p>\n\n\n\n

Build and return an integer array <\/em>result<\/code> with the same length as <\/em>nums<\/code> such that <\/em>result[i]<\/code> is equal to the summation of absolute differences<\/strong> between <\/em>nums[i]<\/code> and all the other elements in the array.<\/em><\/p>\n\n\n\n

In other words, result[i]<\/code> is equal to sum(|nums[i]-nums[j]|)<\/code> where 0 <= j < nums.length<\/code> and j != i<\/code> (0-indexed<\/strong>).<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [2,3,5]\nOutput:<\/strong> [4,3,5]\nExplanation:<\/strong> Assuming the arrays are 0-indexed, then\nresult[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,\nresult[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,\nresult[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [1,4,6,8,10]\nOutput:<\/strong> [24,15,13,15,21]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= nums.length <= 105<\/sup><\/code><\/li>
  • 1 <= nums[i] <= nums[i + 1] <= 104<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Prefix Sum<\/strong><\/h2>\n\n\n\n
    Let s[i] denote sum(num[i] – num[j]) 0 <= j <= i
    s[i] = s[i – 1] + (num[i] – num[i – 1]) * i
    Let l[i] denote sum(nums[j] – nums[i]) i <= j < n
    l[i] = l[i + 1] + (nums[i + 1] – num[i]) * (n – i – 1)
    ans[i] = s[i] + l[i]<\/p>\n\n\n\n
    e.g. 1, 3, 7, 9
    s[0] = 0
    s[1] = 0 + (3 – 1) * 1 = 2
    s[2] = 2 + (7 – 3) * 2 = 10
    s[3] = 10 + (9 – 7) * 3 = 16
    l[3] = 0
    l[2] = 0 + (9 – 7) * 1 = 2
    l[1] = 2 + (7 – 3) * 2 = 10
    l[0] = 10 + (3 – 1) *  3 = 16<\/p>\n\n\n\n
    ans = [16, 12, 12, 16]<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector getSumAbsoluteDifferences(vector& nums) {\n    const int n = nums.size();\n    vector ans(n);    \n    for (int i = 1, sum = 0; i < n; ++i)\n      ans[i] += (sum += (nums[i] - nums[i - 1]) * i);\n    for (int i = n - 2, sum = 0; i >= 0; --i)\n      ans[i] += (sum += (nums[i + 1] - nums[i]) * (n - i - 1));\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an integer array nums sorted in non-decreasing order. Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31,177,376,200],"class_list":["post-7790","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-medium","tag-on","tag-prefix-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7790","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7790"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7790\/revisions"}],"predecessor-version":[{"id":7792,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7790\/revisions\/7792"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7790"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7790"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7790"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}