[LeetCode] 1685. Sum of Absolute Differences in a Sorted Array

https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/description/

Sum of Absolute Differences in a Sorted Array - LeetCode

leetcode - Sum of Absolute Differences in a Sorted Array

문제 유형: 부분합

문제 난이도 : Medium

 

 

문제

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 other elements in the array.

In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).

 

당신은 오름차순의 정수 배열 nums가 있습니다.

result[i] = sum(|nums[i]-nums[j]|) , (0 <= j < nums.length)를 만족하는 배열 result를 반환하시오.

즉, 다른 수들과의 모든 차를 누적한 값 입니다.

 

 

풀이

매번 차이를 구해서 더하는 방식은 시간초과가 난다.

대신, 부분합을 이용해서 값을 빠르게 구할 수 있다.

 

오름차순으로 정렬된 배열에서 차는 뒤쪽의 수에서 앞쪽의 수를 빼는 것이다.

자신보다 앞 인덱스의 수들에 대해서는 자신보다 작은 수들의 합을 (자신보다 작은 수들의 개수) * (현재 자신의 수)에서 빼주면 된다.

자신보다 뒤 인덱스의 수들에 대해서는 자신보다 큰 수들의 합에 (큰 수자들의 개수) * (현재 자신의 수)를 빼주면 된다.

이 양쪽 값을 더해주면 된다.

 

prefix 와 postfix의 부분합을 각각 만든다.

prefix[i]는 0인덱스부터 i 이전까지의 합이다.

postfix[i]는 i이후부터 n-1까지의 합이다.

 

 

코드

C++

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        const int n = nums.size();
        int sum = 0;
        vector<int> prefix(n);
        vector<int> postfix(n);
        vector<int> sumOfAbsoluteDiff(n);
        
        prefix[0] = 0;
        postfix[n-1] = 0;
        for(int i = 1; i < n; i++) {
            prefix[i] = prefix[i-1]+nums[i-1];
            postfix[n-i-1] = postfix[n-i] + nums[n-i];
        }

        for(int i = 0; i < n; i++) {
            sumOfAbsoluteDiff[i] = (i * nums[i]) - prefix[i] + postfix[i] - (n-i-1) * nums[i];
        }

        return sumOfAbsoluteDiff;
    }
};