专栏首页五分钟学算法每天一算: Number of Boomerangs

每天一算: Number of Boomerangs

leetcode上第447号问题:Number of Boomerangs

给定平面上 n 对不同的点,“回旋镖” 是由点表示的元组 (i, j, k) ,其中 i 和 j 之间的距离和 > i 和 k 之间的距离相等(需要考虑元组的顺序)。 找到所有回旋镖的数量。你可以假设 n 最大为 500,所有点的坐标在闭区间 [-10000, 10000] 中。 示例: 输入: [[0,0],[1,0],[2,0]] 输出: 2 解释: 两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

思路

n最大为500,可以使用时间复杂度为 O(n^2)的算法。

  • 遍历所有的点,让每个点作为一个锚点
  • 然后再遍历其他的点,统计和锚点距离相等的点有多少个
  • 然后分别带入n(n-1)计算结果并累加到res中
Tips:
Tip1
  • 如果有一个点a,还有两个点b和c,如果ab和ac之间的距离相等,那么就有两种排列方法abc和acb;
  • 如果有三个点b,c,d都分别和a之间的距离相等,那么有六种排列方法,abc, acb, acd, adc, abd, adb;
  • 如果有n个点和点a距离相等,那么排列方式为n(n-1)。
Tip2
  • 计算距离时不进行开根运算, 以保证精度;
  • 只有当n大于等于2时,res值才会真正增加,因为当n=1时,增加量为1*(1-1)=0

动画演示

代码

 1// 447. Number of Boomerangs
 2// https://leetcode.com/problems/number-of-boomerangs/description/
 3// 时间复杂度: O(n^2)
 4// 空间复杂度: O(n)
 5class Solution {
 6public:
 7    int numberOfBoomerangs(vector<pair<int, int>>& points) {
 8
 9        int res = 0;
10        for( int i = 0 ; i < points.size() ; i ++ ){
11
12            // record中存储 点i 到所有其他点的距离出现的频次
13            unordered_map<int, int> record;
14            for(int j = 0 ; j < points.size() ; j ++){
15                if(j != i){
16                    // 计算距离时不进行开根运算, 以保证精度
17                    record[dis(points[i], points[j])] += 1;
18                }
19            }
20
21            for(unordered_map<int, int>::iterator iter = record.begin() ; iter != record.end() ; iter ++){
22                res += (iter->second) * (iter->second - 1);
23            }
24        }
25        return res;
26    }
27
28private:
29    int dis(const pair<int,int> &pa, const pair<int,int> &pb){
30        return (pa.first - pb.first) * (pa.first - pb.first) +
31               (pa.second - pb.second) * (pa.second - pb.second);
32    }
33};

执行结果

本文分享自微信公众号 - 五分钟学算法(blgczzz),作者:五分钟学算法

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 几道和散列(哈希)表有关的面试题

    散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到...

    五分钟学算法
  • 这道算法题太太太太太简单啦

    题目来源于 LeetCode 上第 268 号问题:缺失数字。题目难度为 Easy,目前通过率为 50.2% 。

    五分钟学算法
  • 位运算中异或的常见用法总结

    异或(^) 这个位操作运算符相信大家一定都不陌生,这个运算符可以用来解决很多普通算法解决不了的问题,而且位运算是直接对二进制码做运算,相对普通的加减乘除运算符来...

    五分钟学算法
  • 弱校联盟10.3

    n对括号最多需要1+2+..+n次交换,当它是)))..(((的形式时,)))(((需要6次,然后把中间两个交换一下,))()((就还需要5次,再交换一次靠近左...

    饶文津
  • 【USACO 3.2】Magic Squares

    4*2个格子分别为 1234 8765 的魔板有3种操作,A:上下两排互换,B:最后一列放到第一列前面,C:中间四个顺时针旋转1格。 现在给出目标状态,...

    饶文津
  • LeetCode31|打印从1到最大的n位数

    这道题算是api的使用方式了,数据的计算,其实自己也没有什么好说的了,但是由于文章的字数必需要达到300字,所有有些时候就只好在这里唠会嗑了,因为文章的原创对于...

    后端Coder
  • 2018 团队设计天梯赛题解---华山论剑组

    2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

    指点
  • 第88场周赛

    第二反应:根据上述这个模拟超时过程,想一优化,shifts数组后面开始,逐个偏移,根据描述,后面的偏移会加到前面。于是有了后缀和这一说法。

    用户1145562
  • 颜色聚合向量

    package com.imageretrieval.features; /** * 颜色聚合向量<br> * 参考链接:http://www.docin...

    Venyo
  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券