题目描述补充

题目：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 示例

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

function distance($p1, $p2) {
    $dx = $p2[0] - $p1[0];
    $dy = $p2[1] - $p1[1];
    return sqrt($dx * $dx + $dy * $dy);
}

function k_nearest_points($points, $query, $k) {
    $distances_and_points = [];
    foreach ($points as $p) {
        $dist = distance($query, $p);
        $distances_and_points[] = [$dist, $p];
    }
    usort($distances_and_points, function($a, $b) {
        return $a[0] - $b[0];
    });
    $result = [];
    foreach (array_slice($distances_and_points, 0, $k) as $item) {
        $result[] = $item[1];
    }
    return $result;
}

// 示例
$points = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10]];
$query = [4, 4];
$k = 3;
print_r(k_nearest_points($points, $query, $k));
?>

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个点的功能。这些示例简单明了，适合作为面试准备或学习算法的参考。码小课网站中还有更多相关内容分享给大家学习，欢迎访问。