Nearest Neighbor

原始题目：LeetGPU - Nearest Neighbor

题目描述

编写一个 GPU 程序，对于设备上存储的 $N$ 个三维点，将 indices[i] 填充为距离 points[i] 最近的点的索引 $j \neq i$。比较平方欧氏距离即可——无需计算平方根：

$$d_{ij}^2 = (x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2$$

实现要求

• solve 函数签名必须保持不变。
• 不允许使用外部库。
• 最终结果必须存储在 indices 数组中。

示例

Input:  points = [(0,0,0), (1,0,0), (5,5,5)], N = 3
Output: indices = [1, 0, 1]  (0↔1互为最近邻，2离1最近)

约束条件

• $1 \le N \le 100{,}000$。
• 坐标为 32 位浮点数，范围 $[-1000, 1000]$。
• 性能测试在 $N = 10{,}000$ 的规模下进行。

解题思路

最近邻搜索的朴素做法是 $O(N^2)$ 的逐对距离计算，对于大 $N$ 不可接受。GPU 上可以并行化：每个线程/block 处理一个查询点，扫描所有候选点。对于 $N = 100{,}000$，可使用分块策略：查询点分到不同 block，每个 block 将候选点分批加载到共享内存中比较，避免重复从全局内存读取。更高效的数据结构如 KD-Tree 或 Ball Tree 在 GPU 上实现较为复杂。欢迎在 GitHub Discussions 分享你的解法。