会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题要交的是题面规定的迭代结果，不是另找一种全局最优划分。初始中心取前 k 个样本。每一轮按曼哈顿距离把样本分到最近的簇，距离相同就留在编号更小的簇。非空簇对每一维单独取中位数：奇数个取排序后正中间一项，偶数个取正中间两项的算术平均；空簇中心保持不动。所有簇、所有维度上新旧坐标绝对差之和小于 10−4 就停止，否则继续，最多 100 轮。最后一轮的簇编号、更新后的中心，以及每个样本到所属中心的曼哈顿距离之和，就是输出的三部分。
中心要单独拷贝，不能和样本共用存储，否则更新中心时会改掉原始特征。分配时先算到 0 号中心的距离，只有严格更近才更换编号，这样并列会落到更小的编号。空簇把旧中心整行抄回去。变化量用双精度累加，再和 10−4 比较。inertia 用这一轮的编号和更新后的中心来算，距离仍然用曼哈顿距离。中心和 inertia 保留 6 位小数；数值为 0 时按正零输出，避免打出 −0.000000。
复杂度分析
最多 T=100 轮。每轮分配要看每个样本到每个中心的每一维，时间 O(Tnkd)。每个簇的每一维排序一次，合计 O(Tdnlogn)。在 n≤5000、k≤100、d≤20 时，分配是主要开销。空间用于存放全部样本和 k 个中心，为 O(nd+kd)。
