K-Means Clustering

原始题目：LeetGPU - K-Means Clustering

题目描述

在 GPU 上实现 K-means 聚类算法（二维点）。给定数据点的 $x$ 和 $y$ 坐标数组、初始质心和迭代参数，将每个点分配到最近的质心，并迭代更新质心。最终质心和标签应存储在输出数组中。

实现要求

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

示例

sample_size=4, k=2, max_iterations=10
data_x=[1,2,8,9], data_y=[1,1,8,8]
init_centroid_x=[1,8], init_centroid_y=[1,8]
→ 点0,1接近质心0, 点2,3接近质心1 → labels=[0,0,1,1]

约束条件

• $1 \le sample\_size \le 100{,}000$，$1 \le k \le 16$，$1 \le max\_iterations \le 100$。
• 坐标和质心为 32 位浮点数。

解题思路

K-means 的每次迭代包含两步：(1) 分配——每个点计算到所有 $k$ 个质心的距离并选最小的；(2) 更新——对每个 cluster 内的点坐标做平均。分配步骤是 $O(N \cdot k)$ 的，每个点完全独立，高度并行。更新步骤需要按 cluster 做坐标求和 + 计数，可以用 atomicAdd 或分块规约实现。欢迎在 GitHub Discussions 分享你的解法。