leetcode:20211216周赛第三题相同元素的间隔之和

leetcode:20211216周赛第三题相同元素的间隔之和
思路:
把相同元素的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

题目深度剖析:
leetcode:20211216周赛第三题相同元素的间隔之和
最终答案:

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

总结:
不要无脑循环,多找找相邻计算单元之间的关系;
降低循环,变成递推!

上一篇:逐行解析Antd Design可编辑单元格


下一篇:1.11 命名切片