当前位置： 面试刷题>> k个最近的点 (经典算法题500道)
### 题目描述补充
题目：**k个最近的点**
给定一个二维平面上的n个点（每个点由(x, y)坐标表示）和一个查询点Q(qx, qy)，请找出距离查询点Q最近的k个点。距离定义为欧几里得距离，即两点(x1, y1)和(x2, y2)之间的距离为sqrt((x2-x1)^2 + (y2-y1)^2)。
### 示例代码
以下是使用Python、PHP和JavaScript编写的示例代码，用于找到距离查询点最近的k个点。
#### Python 示例
```python
import math
from typing import List, Tuple
def distance(p1: Tuple[float, float], p2: Tuple[float, float]) -> float:
return math.sqrt((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2)
def k_nearest_points(points: List[Tuple[float, float]], query: Tuple[float, float], k: int) -> List[Tuple[float, float]]:
# 使用列表推导和排序（按距离）
distances_and_points = sorted([(distance(query, p), p) for p in points])
return [p for _, p in distances_and_points[:k]]
# 示例
points = [(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)]
query = (4, 4)
k = 3
print(k_nearest_points(points, query, k))
```
#### PHP 示例
```php
```
#### JavaScript 示例
```javascript
function distance(p1, p2) {
const dx = p2[0] - p1[0];
const dy = p2[1] - p1[1];
return Math.sqrt(dx * dx + dy * dy);
}
function kNearestPoints(points, query, k) {
return points
.map(p => [distance(query, p), p])
.sort((a, b) => a[0] - b[0])
.slice(0, k)
.map(item => item[1]);
}
// 示例
const points = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10]];
const query = [4, 4];
const k = 3;
console.log(kNearestPoints(points, query, k));
```
以上代码分别用Python、PHP和JavaScript实现了查找二维平面上距离查询点最近的k个点的功能。这些示例简单明了，适合作为面试准备或学习算法的参考。码小课网站中还有更多相关内容分享给大家学习，欢迎访问。