算法笔试模拟题精解之“能量半径”-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

算法笔试模拟题精解之“能量半径”

简介: 题目的含义就是找到距离原点最近的第k个点,并求它的半径。这个题的关键在于排序算法。使用最简单的冒泡排序,时间复杂度O(n^2);使用快速排序等好一点的排序算法,时间复杂度O(nlog(n));也可以使用java中Arrays类中的sort函数。
+关注继续查看

在线编程介绍

阿里云开发者社区在线编程产品,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,为用户营造专心答题的学习环境。点击链接开始体验:https://developer.aliyun.com/coding

本文为大家介绍其中的 第61题:能量半径 的题目解析,具体如下:

题目描述

题目等级:中等
知识点:二分查找、树状数组

查看题目:能量半径 codancer来到了一个能量平面上的中心,坐标为(0,0),接下来巫师Tom会在q个坐标上放置能量点,每个能量点的能量值为1,为了打败哥斯拉,他需要至少k点的能量,因此他想确定一个最小的整数半径r使得codancer能够从这个圆心为(0,0),半径为r的圆形区域内得到至少k个能量值,请你帮他确定最小的整数半径r。

输入包含三个部分,第一个输入能量点的个数q(1<=q<=100000),第二个输入必须获得的最小能量值k(0<=k<=q),第三个是q个坐标(xi,yi),(-100000<=xi<=100000,-100000<=yi<=100000并且xi和yi都是整数)。
输出一个正整数r,表示最小的半径。
示例1
输入:
4
3
[[1,1],[-1,1],[-1,-1],[2,3]]
输出:
2
注意
当半径为2的时候可以收集到1,1,[-1,-1]处的能量。

解题思路:排序算法

题目的含义就是找到距离原点最近的第k个点,并求它的半径。
计算过程:

  1. 计算每个点到原点的距离,为了减少计算量可以只计算到平方。使用long[n]这样的数组来保存。使用long类型是为了防止平方之后结果超出int类型范围。
  2. 对距离进行从小到大排序
  3. 取排序后的第k个数值开根号,转化为int类型并加1。加1是因为开根号后可能为小数,转化成int类型会直接舍去小数部分,导致结果比实际小一些。

这个题的关键在于排序算法。

使用最简单的冒泡排序,时间复杂度O(n^2);
使用快速排序等好一点的排序算法,时间复杂度O(nlog(n));
也可以使用java中Arrays类中的sort函数。

看完之后是不是有了想法了呢,快来练练手吧>>查看题目:能量半径
image.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
比特币系统采用的公钥密码学方案和ECDSA签名算法介绍——第一部分:原理
ECC算法是基于有限域的椭圆曲线上的数学算法。关于ECC算法基本原理的介绍,请参考《ECC加密算法入门介绍》(http://www.8btc.com/eccmath),本文重点介绍Bitcoin系统中采用的公钥密码学方案和签名算法的实现细节。
1511 0
NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2
大家好,我是小笨笨,今天我们继续来讲解模拟算法。 我们直接上例题! 栗1.1.2-1 洛谷P1014 Cantor表https://www.luogu.org/problemnew/show/P1014题目描述现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。
948 0
进化算法可以不再需要计算集群,开普敦大学的新方法用一块GPU也能刷新MNIST记录
他们实验中只使用了一块GTX1070 GPU,训练时间6到24小时,就可以取得这样的成果,他们觉得非常满意。他们的研究也首次尝试了把神经进化用在一维卷积网络的创造中,用来解决情感分析、包括嵌入层的优化问题。
1297 0
算法笔试模拟题精解之“恐怖的辐射”
因为N M 和最大辐射值都不大,所以可以直接模拟辐射扩散的实际情况,最后判断是否有小于等于7的位置。
324 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4478 0
算法题——投篮比赛获胜概率问题
问题描述: 甲乙两人比赛投篮。约定甲先投篮,每人投篮投进一球,则继续投球,若投失一球,则换人投球。初始积分为1分,甲每投进一球,积分加1分;乙每投进1球,积分减1分。若积分达到N分(N>1),甲获胜;若积分减至0分,乙获胜。
733 0
合辑 | 10+笔试算法模拟题精解,带你玩转算法!
阿里云开发者社区在线编程频道部分笔试算法模拟题题目解析合辑,参与做题的同学快来对答案啦!
4357 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载