页面加载中…
AI024. K-Means++ 确定性初始化
中等通过率 0% · 提交 0 · 通过 0
华为 AI 岗K-Means初始化距离
改编自算法机考高频题型 · 华为 AI 岗 / K-Means类型 · 难度：中等
给定 n 个 d 维整数样本(编号从 0 开始)和目标中心数 k,按下面的确定性规则选出 k 个初始中心: 1. 第 1 个中心固定为编号 0 的样本。 2. 之后每轮,对每个尚未成为中心的样本 x,计算它到所有已选中心的欧氏距离平方,记最小值为 D(x);选 D(x) 最大的样本作为新中心,若多个样本的 D(x) 相同,选编号最小的。 重复第 2 步直到选满 k 个中心,按选取顺序输出这 k 个样本的编号。
这类题属于算法机考高频题型中「华为 AI 岗 / K-Means」方向的高频题型，通常考察对「华为 AI 岗 / K-Means」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
输入描述
第一行输入三个整数 n d k。接下来 n 行,每行输入 d 个整数,表示一个样本。
输出描述
输出一行 k 个整数,以单个空格分隔,表示按选取顺序排列的中心编号。
示例
示例 1
输入示例
3 1 2 0 10 3
输出示例
0 1
说明：
到中心 0 的距离平方 100 大于 9
示例 2
输入示例
4 2 3 0 0 0 0 5 5 5 5
输出示例
0 2 1
说明：
重复样本点:第三轮全部 D(x)=0,取编号最小的 1
时间限制 3000 ms · 内存限制 256 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
⚠️ 这道题的坑 · 易错点与反直觉
这些是真正决定能不能 AC、但通用题解里常被略过的点。
- 每轮全量重算距离是超时主因,minDist 只会被新中心刷新
- 重复样本点 D(x)=0 仍是合法候选,跳过它们在全零轮次会选错
- 并列取编号小:用严格大于更新最优,天然满足
解题思路
这道题在考什么
课程第 9 天补学里那句「k-means++ 把初始中心尽量选得互相远」在这里落成可判题的确定性版本:去掉随机采样,改成「每轮选 D(x) 最大的样本」。考点有两个:增量维护最小距离的效率意识,和「未选样本里挑 + 并列取编号小」的规则落实。
核心量:D(x) 的增量维护
D(x) = 样本 x 到所有已选中心的最小平方距离。朴素写法每轮对每个样本重算到全部中心的距离,O(n·k²·d),n = 10⁴、k = 100 时 10⁹ 量级,会超。正解是增量维护:
minDist[x] 初始化为 x 到中心 0 的距离
每选出一个新中心 c:
minDist[x] = min(minDist[x], dist2(x, c)) # 只算到新中心这一个距离每轮 O(n·d),总 O(n·k·d) = 8×10⁶,轻松。这一步就是「多了一个中心,每个样本的最小值只可能被新中心刷新」的单调性,想通了代码只有两行。
选取规则逐条落实
- 第 1 个中心固定编号 0,无条件。
- 每轮只在尚未成为中心的样本里挑 D(x) 最大者;并列取编号最小。顺序遍历、用严格大于来更新最优,天然满足「并列取小」。
- 重复样本点的用例(示例 2)是试金石:已选中心的坐标再次出现时,那些副本的 D(x) = 0,但它们仍是合法候选——当全部剩余样本 D(x) 都是 0 时,选编号最小的那个副本。「跳过 D(x)=0 的样本」是想当然的错误优化。
整数世界
坐标是整数,平方距离全程整数,不需要浮点、不存在精度并列的歧义——这也是「确定性初始化」可判题的原因。最大单距离 8×(2000)² = 3.2×10⁷,int 够,64 位更省心。
易错点展开
- 每轮全量重算距离:超时的主因。
- 把已选中心也当候选:会重复选中同一个点。
- 并列规则用了「后见者覆盖」(>= 更新):选出编号大的,判题必挂。
- D(x)=0 的样本被跳过:重复点用例专卡这个。
参考实现怎么读
参考实现三个数组:样本坐标、minDist、chosen 标记。选第 1 个中心后初始化 minDist,然后 k-1 轮:线性扫未选样本取 minDist 最大者(严格大于才更新,天然并列取小),选中后再扫一遍用新中心刷新所有未选样本的 minDist。两次线性扫都是 O(n·d),没有任何堆或排序——这道题的正解朴素得令人放心,难点只在别多算。
增量维护为什么对
新增一个中心,任何样本到「所有中心」的最小距离只可能因为新中心而变小,老中心的贡献都已经沉淀在 minDist 里。所以每轮只算「到新中心」这一个距离。这个单调性和课程第 9 天 K-Means 里「分配步不会让 inertia 变大」是同一类论证——最小值只朝一个方向走。
写完先自查这三组
1. 样例 1:minDist 初始 [0, 100, 9],最大 100 在编号 1,输出 0 1。 2. 样例 2 的重复点:第三轮剩余样本 minDist 全 0,取编号最小的 1——跳过零距离的实现会在这里选错或选不出。 3. k = n:全部样本都会被选,输出顺序由每轮的 D(x) 决定而不是编号顺序,验证「按选取顺序输出」。
参考代码
# k-means++ 确定性版:minDist[x] 增量维护,每选一个新中心只算一次新距离
# 每轮在未选样本里取 D(x) 最大、并列取编号小;整数平方距离零浮点
import sys
def solve() -> None:
data = sys.stdin.buffer.read().split()
if not data:
return
n = int(data[0]); d = int(data[1]); k = int(data[2])
pts = []
at = 3
for _ in range(n):
pts.append([int(data[at + j]) for j in range(d)])
at += d
chosen = [False] * n
order = [0]
chosen[0] = True
INF = float("inf")
min_dist = [INF] * n
last = 0
for _ in range(k - 1):
lp = pts[last]
for i in range(n):
if chosen[i]:
continue
p = pts[i]
s = 0
for j in range(d):
diff = p[j] - lp[j]
s += diff * diff
if s < min_dist[i]:
min_dist[i] = s
best = -1
best_val = -1
for i in range(n):
if not chosen[i]:
v = min_dist[i]
if v > best_val:
best_val = v
best = i
chosen[best] = True
order.append(best)
last = best
sys.stdout.write(" ".join(map(str, order)) + "\n")
solve()
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
