Re: [閒聊] 每日leetcode
2615. Sum of Distances
題目：
給你一個int陣列nums，找出一個與nums一樣長的long陣列arr
其中arr[i] 為 |i-j| 的總和，j的條件為 nums[j]==nums[i] 且 j!=i
如果j不存在則設定arr[i]=0
思路：
也就是陣列裡只有相同的數字需要計算，沒有相同的數字就是設0
所以先統計每個數字在陣列裡出現幾次以及記錄他們的index
然後再用PrefixSum的技巧計算每個index左右兩側的和
C#
public long[] Distance(int[] nums)
{
var groups = new Dictionary<int, List<int>>();
for (int i=0;i<nums.Length;i++)
{
if (groups.ContainsKey(nums[i]))
{
groups[nums[i]].Add(i);
}
else
{
groups.Add(nums[i], new List<int>{i});
}
}
var result = new long[nums.Length];
foreach (var group in groups.Values)
{
var numCount = group.Count;
if (numCount == 1)
{
continue;
}
var prefixSum = new long[numCount + 1];
for (int i=0;i<numCount;i++)
{
prefixSum[i+1] = prefixSum[i] + group[i];
}
for (int i=0;i<numCount;i++)
{
long index = group[i];
long leftSum = index * i - prefixSum[i];
long rightSum = (prefixSum[numCount] - prefixSum[i+1]) -
index * (numCount-1-i);
result[index] = leftSum + rightSum;
}
}
return result;
}
這裡太久沒人寫，連標題都消失了
我當初從潛水到越來越常來的其中一個原因就是感覺這裡有很多碼農
很多人每天寫這個會有種很多人一起努力的感覺
而現在可能大家都找到理想工作就不刷題了
我自己則是腳麻而且刷題實在太累，好久沒寫就會容易忘記
這題其實也是雖然大概知道怎麼解，但也要偷看答案才能把PrefixSum最後的部分寫出來= =
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.21.14 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1776967943.A.F6E.html
推
04/24 02:38,
3周前
, 1F
04/24 02:38, 1F
→
04/24 03:12,
3周前
, 2F
04/24 03:12, 2F
推
04/24 03:13,
3周前
, 3F
04/24 03:13, 3F
討論串 (同標題文章)
完整討論串 (本文為第 1566 之 1566 篇)：