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

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

贡献者 | 黄信旭

简介：题目的含义就是找到距离原点最近的第 k 个点，并求它的半径。这个题

的关键在于排序算法。使用最简单的冒泡排序，时间复杂度 O(n^2)；使用快速排序

等好一点的排序算法，时间复杂度 O(nlog(n))；也可以使用 java 中 Arrays 类中的

sort 函数。

题目描述

题目等级：中等

知识点：二分查找、树状数组

查看题目：能量半径

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

输入：

3

[[1,1],[-1,1],[-1,-1],[2,3]]

输出：

2

注意

当半径为 2 的时候可以收集到 1,1,[-1,-1] 处的能量。

解题思路：排序算法

题目的含义就是找到距离原点最近的第 k 个点，并求它的半径。

计算过程：

1. 计算每个点到原点的距离，为了减少计算量可以只计算到平方。使用

long[n] 这样的数组来保存。使用 long 类型是为了防止平方之后结果超出

int 类型范围。

1. 对距离进行从小到大排序
2. 取排序后的第 k 个数值开根号，转化为 int 类型并加 1。加 1 是因为开根号后

可能为小数，转化成 int 类型会直接舍去小数部分，导致结果比实际小一些。

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

使用最简单的冒泡排序，时间复杂度 O(n^2)；

使用快速排序等好一点的排序算法，时间复杂度 O(nlog(n))；

也可以使用 java 中 Arrays 类中的 sort 函数。

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