力扣2615. 等值距离和

发布于:2025-07-03 ⋅ 阅读:(24) ⋅ 点赞:(0)

在这里插入图片描述
由数据范围是10^5,只能一次遍历,暴力是别想了,
看到arr[i] 等于所有 |i - j| 之和,这很明显是求距离和的方法—数学公式推导+前缀和
下面这一题也有类似的思路

1685. 有序数组中差绝对值之和

那我们如何处理满足 nums[j] == nums[i] 且 j != i 的所有 j这个条件呢?
我们可以用哈希表来存储,对于相同元素的值的下标/索引,我们可以选择把它存在一一个数组里面
也就是

         unordered_map<int,vector<int>> mp;
        for(int i=0;i<nums.size();i++)
        {
           mp[nums[i]].push_back(i);
		}

这样具有相同的值的下标就到一个数组里面了!
然后,
我们可以取哈希表中的key值
得到一个索引数组(就是上文提到的对于相同元素的值的下标/索引,我们可以选择把它存在一一个数组里面)
我们只需要对这个数组中的每一个元素求一下 |i - j| 之和也就是sum(abs(i-j))
我们已知了装有i,j的数组(索引数组)那求起来就很好求
只需要对sum(abs(i-j))展开
因为带有绝对值,所以我们分成两部分
(这里就是把式子展开,具体可以自己列列式子和合并同类项)

sumleft和sumright
sumleft=index*i-sum[i]
sumright=(sum[a.size()]-sum[i+1])-index*(a.size()-(i+1));
sum=sumleft+sumright;

这样我们就求出了一个索引i它的sum(abs(i-j))的值
也就是题目中arr数组中的一个元素。
因此我们就可以写代码了

class Solution {
public:
 long long sum[100005];
unordered_map<int,vector<int>> mp;
 vector<long long> distance(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
        {
           mp[nums[i]].push_back(i);
          
		}
		vector<long long> result(nums.size());
		for(auto q:mp)
        {
		  vector<int> a=q.second;
		   for(int i=0;i<a.size();i++)
		   {
		      sum[i+1]=sum[i]+a[i];	
		   } 
		   for(int i=0;i<a.size();i++)
		   {
		      int index=a[i];
			  long long sumleft=(long long)index*i-sum[i];
			  long long sumright=(sum[a.size()]-sum[i+1])-(long long)index*(a.size()-(i+1));	
		      long long sum=sumleft+sumright;
		      result[index]=sum;
		   } 
	    }        
        return result;
        
        
    }
};

需要注意的是要开long long ,不仅是前缀和需要开long long ,在算sumleft和sunright的过程中遇到乘法的时候也需要开long long,这一点不得不防。
时间复杂度O(n)
这里是双重循环,但不代表是O(n^2)因为每次从哈希表中取数据是O(1)。


网站公告

今日签到

点亮在社区的每一天
去签到