一.初始化聚类中心 根据题目要求，直接从数据点中取前 k 个点作为初始中心： centers[0..k-1] = nums[0..k-1]。

二.重复迭代（最多 max_iter 次） 每次迭代分为两步：

1）分配簇标签（Assignment Step） 对于每个点 nums[i] = (xi, yi)：

• 计算到每个中心 centers[j] 的欧氏距离的平方（不用开根号，比较平方即可）
• 选取距离最小的中心 j，将该点的标签设为 labels[i] = j
• 如果标签发生变化，则说明本轮有更新

2）更新聚类中心（Update Step）

• 对每个簇 j 统计所有被分到簇 j 的点的坐标和及数量：

  • sumX[j]、sumY[j]、cnt[j]

• 若 cnt[j] > 0，则新中心为：

  • centers[j].x = sumX[j] / cnt[j]
  • centers[j].y = sumY[j] / cnt[j]

• 若某个簇本轮没有点（cnt[j] == 0），可以简单地保持原中心不变，避免除零与复杂操作。

三.收敛判断（提前结束） 如果某一轮迭代中，所有点的标签都没有发生变化（即没有任何 labels[i] 更新），说明算法已经收敛，可以提前退出循环。

class Solution:
    def kMeans(
        self,
        n: int,
        k: int,
        max_iter: int,
        nums: List[List[float]]
    ) -> Tuple[List[List[str]], List[int]]:
        """
        n: 点的数量
        k: 聚类簇的数量
        max_iter: 最大迭代次数
        nums: 点的坐标列表 [[x1, y1], [x2, y2], ...]
        返回值: (centers_str, labels)
            centers_str: 每个中心坐标为 4 位小数的字符串 [["1.2345","2.0000"], ...]
            labels: 每个点所属的簇编号 [c0, c1, ...]
        """
        # 初始化聚类中心：直接取前 k 个点（浮点计算）
        centers = [[float(nums[i][0]), float(nums[i][1])] for i in range(k)]
        # 初始化每个点所属的簇标签，初始为 -1 表示未分配
        labels = [-1] * n

        for _ in range(max_iter):
            changed = False  # 标记本轮是否有标签变化

            # 第一步：为每个点分配最近的簇
            for i in range(n):
                x, y = nums[i]
                best_cluster = 0
                # 初始距离取到第 0 个中心
                dx = x - centers[0][0]
                dy = y - centers[0][1]
                best_dist = dx * dx + dy * dy

                # 遍历其他中心，找到最近的
                for j in range(1, k):
                    dx = x - centers[j][0]
                    dy = y - centers[j][1]
                    dist = dx * dx + dy * dy
                    if dist < best_dist:
                        best_dist = dist
                        best_cluster = j

                # 如果标签发生变化，记录下来
                if labels[i] != best_cluster:
                    labels[i] = best_cluster
                    changed = True

            # 如果本轮没有任何标签变化，说明已经收敛，提前结束
            if not changed:
                break

            # 第二步：根据新标签更新每个簇的中心
            sum_x = [0.0] * k
            sum_y = [0.0] * k
            count = [0] * k

            # 累加每个簇中的点坐标和
            for i in range(n):
                c = labels[i]
                sum_x[c] += nums[i][0]
                sum_y[c] += nums[i][1]
                count[c] += 1

            # 计算新的中心坐标（浮点数）
            for j in range(k):
                if count[j] > 0:
                    centers[j][0] = sum_x[j] / count[j]
                    centers[j][1] = sum_y[j] / count[j]
                # 如果某个簇没有点，可以选择保持原中心不变

        # 把中心转换成「固定 4 位小数」的字符串形式，补足尾部 0
        centers_str: List[List[str]] = []
        for x, y in centers:
            centers_str.append([f"{x:.4f}", f"{y:.4f}"])

        return centers_str, labels

题面描述

实现一个二维数据的 K-Means 聚类算法。

给定：

• 一个整数 n 表示数据点数量；
• 一个整数 k 表示聚类数；
• 一个整数 max_iter 表示最大迭代次数；
• 一个二维数组 nums，其中 nums[i] = [xi, yi] 表示第 i 个二维数据点的坐标。

你需要对 nums 中的 n 个点进行 K-Means 聚类，将它们划分为 k 个簇。在聚类过程中，允许最多进行 max_iter 次迭代（如果在此之前收敛则可以提前停止）。初始聚类中心:从数据点中选择读入进来的前 k 个点作为初始中心。

算法结束后，需要返回两个结果：

1. 一个长度为 k 的二维数组，表示最终的聚类中心坐标，形式为
   [[x1, y1], [x2, y2], ..., [xk, yk]]。
2. 一个长度为 n 的整数数组，表示每个数据点所属的聚类标签，标签范围为 [0, k - 1]，顺序与 nums 中数据点的顺序一致。

注意:保留4位小数，误差容忍度 1e-3

示例

输入：

n = 4 , k = 2 , max_iter = 100
nums = [[1.0,1.0],[1.5,2.0],[5.0,8.0],[8.0, 8.0]]

输出：

[[1.25,1.5],[6.5,8.0]]
[0,0,1,1]

数据范围:

1 <= n <= 2 * 10^4

1 <= k <= 20

1 <= max_iter <= 100

-1e4 <= nums[i][0], nums[i][1] <= 1e4