526互联

6360.等值距离和-340

发布时间 2023-04-09 20:41:03作者: huangxk23

等值距离和

给你一个下标从 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 。

提示：

\(1 <= nums.length <= 10^5\)
\(0 <= nums[i] <= 10^9\)
通过次数3,062提交次数10,354

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sum-of-distances
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1：哈希表

首先自然的想法是使用哈希表记录每一个元素的位置，再遍历哈希表计算每一个元素和相等位置的元素的差值。超时。考虑最极端的情况，就是数组中的元素全部相同的情况下，通过遍历的方式计算相同元素的位置差值的和时间复杂度也是O(n^2)的。

code

class Solution {
public:
    //全是相同的数。。。。
    //10 ^ 5 * 10 ^ 5
    //哈希表实际上就是两次遍历啊
    //两次遍历的原因：计算a时abs(a,b)计算b时abs(a,b)
    
    vector<long long> distance(vector<int>& nums) {
        
        unordered_map<int,deque<int>> position;
        
        for(int i = 0;i < nums.size();i ++)
        {
            position[nums[i]].push_back(i);
        }
        
        int n = nums.size();
        vector<long long int> ans(n,0);
        
        long long int tmp = 0;
        for(int i = 0;i < nums.size();i ++)
        {
            
            for(int j = 1;j < position[nums[i]].size();j++)
            {
                tmp = abs(i - position[nums[i]][j]);
                ans[i] += tmp;
                ans[position[nums[i]][j]] += tmp;
            }
            position[nums[i]].pop_front();
            
        }
        
        return ans;
    }
};

解题思路2：前缀和

问题的关键是，对于哈希表中相同元素位置的有序数组vector，如何在O(n)的时间复杂度时间内计算每一个元素和其余元素之间差值的绝对值之和（当时还是急躁了，没有认真的分清楚一个个的子问题，想到了前缀和但是没有认真思考怎么做，功利心太重了，老是想着提高排名，还是要自然一点，做出来就行）。由于vector记录的是同一个元素出现的位置也就是有序的，那么如何计算vector中的一个元素nums和其余元素之间的差值呢。首先计算全部的前缀和，实际上可以分为两个部分进行处理：

  1. 一个是小于nums[i]的，结果是i * nums[i] - prefix[i]
  2. 一个是大于nums[i]的，结果是prefix[nums.size() -1] - prefix[i] - nums[i] * (nums.size() -1)
  3. nums[i]和其余元素之间的差值就是两个部分的和

顺便学习了一个新得语法：1LL，乘上一个1LL可以将int类型转换为 long long int 类型并且将计算结果保存在long long int类型变量中。

code

class Solution {
public:

    void get_ans(vector<int> & p,vector<long long int> & ans)
    {
        int len = p.size();
        vector<long long int> prefix(len,0);
        prefix[0] = p[0];

        for(int i = 1;i < len;i ++) prefix[i] = prefix[i-1] + p[i];

        long long int l_sum = 0,r_sum = 0;

        for(int i = 0;i < len;i ++)
        {
            l_sum =  1LL * (i + 1) * p[i] - prefix[i];
            r_sum = prefix[len - 1] - prefix[i] - 1LL * p[i] * (len - i - 1);
            ans[p[i]] = l_sum + r_sum;         
        }
    }
    vector<long long> distance(vector<int>& nums) {

        int n = nums.size();

        unordered_map<int,vector<int>> position;

        for(int i = 0;i < nums.size();i ++)
            position[nums[i]].push_back(i);

        vector<long long int> ans(n,0);

        for(auto p : position)
        {
            get_ans(p.second,ans);
        }   

        return ans;
    }
};