算法筆試模拟題精解之“能量半徑”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

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函數。

看完之後是不是有了想法了呢，快來練練手吧>>