思路:
把相同元素的index存到一个list里面
然后挨个求函数(超时了)
这道题的本质就是如何快速地求:
一个递增list中,每个数到其他数的距离之和(距离之和可以通过递推求,用循环超时)
我的超时循环做法:
class Solution:
def getDistances(self, arr: List[int]) -> List[int]:
record = {}
# 放入每个key的位置,形成list
for i in range(len(arr)):
if arr[i] not in record:
record[arr[i]] = [i]
else:
record[arr[i]].append(i)
# 遍历输出结果
res = []
for i in range(len(arr)):
#print(record[arr[i]])
tempans = 0
for index in record[arr[i]]:
tempans += abs(i - index)
res.append(tempans)
return res
题目深度剖析:
最终答案:
class Solution:
def getDistances(self, arr: List[int]) -> List[int]:
# 归纳所有数字对应的index
record = collections.defaultdict(list)
for index, val in enumerate(arr):
record[val].append(index)
#print(record)
n = len(arr)
ans = [0] * n
for v in record.values():
m = len(v)
now = sum(v) - v[0] * m
for i in range(len(v)):
diff = v[i] - v[i - 1] if i > 0 else 0
now += i * diff - (m - i) * diff
ans[v[i]] = now
return ans
总结:
不要无脑循环,多找找相邻计算单元之间的关系;
降低循环,变成递推!