在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：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函数。

看完之后是不是有了想法了呢，快来练练手吧>>查看题目：能量半径