文章目录

• • • 原题题目
    • 代码实现（首刷自解复杂度较高）
    • 代码实现（首刷自解优化）

原题题目

代码实现（首刷自解复杂度较高）

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int size = nums.size(),lowertimes = size,lower = 0,highertimes = 0 ;
        vector<int> ret;
        unordered_map<int,int> map;
        for(const auto& num:nums)
        {
            lower += num;
            ++map[num];
        }   

        for(int i=0;i<size;++i)
        {
            if(i && nums[i] > nums[i-1])
            {
                lowertimes -= 2*map[nums[i-1]];
                lower -= 2*nums[i-1]*map[nums[i-1]];
            }
            int temp = lower - (lowertimes)*nums[i];
            ret.emplace_back(temp);
        }
        return ret;
    }
};

代码实现（首刷自解优化）

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int size = nums.size(),times = size-1;
        vector<int> ret,l(nums.size()),r(l);
        for(int i=0,temp=0;i<nums.size();)   l[i++] = (temp += nums[i]);
        for(int i=nums.size()-1,temp=0;i>=0;)   r[i--] = (temp += nums[i]);
        
        for(int i=0,temp=1;i<nums.size();++i,times-=2)
        {
            int num = r[i]-l[i]-(times)*nums[i];
            ret.emplace_back(num);
        }
        return ret;
    }
};