关于leetcode:LeetCode-447-Number-of-Boomerangs-回旋镖个数-时间复杂度On²

解题思路

1. 因为[i,j,k]三元组中i的地位是惟一的，所以咱们能够固定i位对数组points进行遍历。
2. 由高中学的排列组合的常识咱们失去，以points[i]为i点、间隔为l的boomerang的个数等于x*（x-1）（也就是A（x,2）），其中x为与points[i]的间隔等于l的点的个数。
3. 咱们只有把这些x*（x-1）都加起来就能失去题目的答案

步骤

1. 遍历数组points，将每个元素points[i]设置为[i,j,k]中的i点
2. 再次遍历数组points，计算从points[i]到其余点的间隔的平方（因为间隔的平方与间隔是一一对应的关系，这里应用间隔的平方以节俭计算工夫），将这些间隔的平方贮存在列表list_distance中
3. 应用计数器cnt计算list_distance中每个数字呈现的次数x
4. 将x*（x-1）累计入num_boomerang

原题链接
欢送在我的博客轻松摸索更多思路

代码

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:

        from collections import Counter
        
        if len(points)==1:
            return 0

        num_boomerang=0

        for i in range(len(points)):
            list_distance=[]
            for j in range(len(points)):
                if j==i:
                    continue
                else:
                    list_distance.append(pow(points[i][0]-points[j][0],2)+pow(points[i][1]-points[j][1],2))

            cnt=Counter(list_distance)
            for k in cnt:
                if cnt[k]>1:
                    num_boomerang+=cnt[k]*(cnt[k]-1)

        return int(num_boomerang)