给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ,arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ,则令 arr[i] 等于 0 。

返回数组 arr 。

示例 1:
输入:nums = [1,3,1,1,2]
输出:[5,0,3,4,0]
解释:
i = 0 ,nums[0] == nums[2] 且 nums[0] == nums[3] 。因此,arr[0] = |0 - 2| + |0 - 3| = 5 。
i = 1 ,arr[1] = 0 因为不存在值等于 3 的其他下标。
i = 2 ,nums[2] == nums[0] 且 nums[2] == nums[3] 。因此,arr[2] = |2 - 0| + |2 - 3| = 3 。
i = 3 ,nums[3] == nums[0] 且 nums[3] == nums[2] 。因此,arr[3] = |3 - 0| + |3 - 2| = 4 。
i = 4 ,arr[4] = 0 因为不存在值等于 2 的其他下标。

示例 2:
输入:nums = [0,5,3]
输出:[0,0,0]
解释:因为 nums 中的元素互不相同,对于所有 i ,都有 arr[i] = 0 。

在这里插入图片描述

相同元素分组+前缀和

class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
        //left=(a[i]−a[0])+(a[i]−a[1])+...+(a[i]−a[i−1])
        int n = nums.size();
        unordered_map<int, vector<int>> groups;
        for(int i = 0; i < nums.size(); i++){
            groups[nums[i]].push_back(i);
        }

        vector<long long> ans(n);
        vector<long long> s(n+1);
        s[0] = 0;
        for(auto& [_, a] : groups){
            int m = a.size();
            for(int k = 0; k < m; k++){
                s[k + 1] = s[k] + a[k];
            }
            for(int i = 0; i < m; i++){
                long long target = a[i];    //储存的是nums中的实际下标
                long long left = target * i - s[i];
                long long right = s[m] - s[i] - target * (m-i);
                ans[target] = left + right;
            }
        }
        return ans;
    }
};

这道题先建立一个数组group,group的键用来储存相同的元素,然后group的值来储存他们分别的在nums中的下标。

接下来是计算部分,对group进行遍历,在遍历的过程中,对相同元素的下标计算前缀和。接着,对group对应键的值里储存的下标进行遍历。再次解释一下为什么要将相同的元素下标放在一起,因为当我们遍历相同元素中的下标的时候,他只需要寻找与这个容器中其他元素的差的绝对值即可。所以遍历的时候,由于容器中的下标是按升序进行排放的,所以计算左半部分的时候就是left=(a[i]−a[0])+(a[i]−a[1])+...+(a[i]−a[i−1]),进行化简后就是target * i - s[i],同理右半部分也是一样,s[m] - s[i] 是右半部分的子段和,然后减去target * (m-i)。最后两者相加,返回对应下标的ans即可。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部