页面加载中…
AI015. 非极大值抑制
中等通过率 0% · 提交 0 · 通过 0
华为 AI 岗NMS贪心目标检测
算法机考高频题型改编 · 聚焦「华为 AI 岗 / NMS」 · 难度：中等
检测模型会对同一个目标输出多个重叠的候选框,需要用非极大值抑制(NMS)去重。规则:按分数从高到低处理候选框,分数相同时先处理输入下标更小的;轮到一个尚未被压掉的框时保留它,并把与它 IoU 严格大于阈值 T 的所有还未处理的框压掉;被压掉的框不再参与后续处理。IoU 的定义与坐标约定同「IoU 矩阵」一题:宽 = x2 - x1,只相接记 0。
这类题属于算法机考高频题型中「华为 AI 岗 / NMS」方向的高频题型，通常考察对「华为 AI 岗 / NMS」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
输入描述
第一行输入 N T,分别是候选框数量与抑制阈值。接下来 N 行,每行 5 个实数 x1 y1 x2 y2 score。
输出描述
输出一行:被保留框的原始下标(从 0 开始),按保留顺序(即分数从高到低、同分下标小者在前)排列,用单个空格分隔。
示例
示例 1
输入示例
3 0.30 0 0 4 4 0.90 1 1 5 5 0.80 10 10 12 12 0.70
输出示例
0 2
说明：
高分框压掉重叠框
示例 2
输入示例
3 0.20 0 0 4 2 0.90 2 0 6 2 0.80 4 0 8 2 0.70
输出示例
0 2
说明：
链式:被压掉的框不再压别人
时间限制 2000 ms · 内存限制 256 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
⚠️ 这道题的坑 · 易错点与反直觉
这些是真正决定能不能 AC、但通用题解里常被略过的点。
- 压制条件是严格大于:IoU 恰等于阈值不压,T=0 时相接框互不压制
- 只有被保留的框有资格压人,两两互压的写法在链式场景必错
- 输出是原始下标按保留顺序,不是排序后的位置
解题思路
这道题在考什么
NMS 是检测后处理的第二件套:模型对同一个目标吐出一堆重叠框,按分数贪心保留、按 IoU 压制重复。规则本身四句话,机考把分数并列、链式压制、输出顺序这些「可复现性细节」全部写死,考你逐条落实的能力。
先把处理顺序定死
排序键是 (分数降序, 下标升序)。同分时先处理下标小的——这条不落实,结果不唯一,判题必挂。课程第 15 天的写法直接用:order = sorted(range(n), key=lambda i: (-score[i], i))。
贪心主循环
按 order 逐个看:如果这个框已被压掉,跳过;否则保留它,并把与它 IoU 严格大于 T 的、还没处理到的框标记为压掉。两个细节:
- 「严格大于」:IoU 恰好等于阈值时不压。T=0 时两个只相接的框(IoU=0)互不压制,T=1 时连完全重合的框也压不掉彼此(IoU=1 不大于 1)——这两个极端用例都在数据里。
- 链式:被压掉的框从此退出舞台,不再压别人。示例 2 就是这个场景:0 压掉 1,1 已死,所以 2 活下来。写法上,只有「当前保留的框」有资格压人,天然满足这条,别写成「任何高分框都压低分框」的两两版本。
输出
输出保留框的原始下标、按保留顺序(即处理顺序)排列。别排序回编号顺序,也别输出排序后的位置。
复杂度与数据范围
N ≤ 300,O(N²) 的两两 IoU 加贪心随便过。IoU 计算沿用上一题:宽 = x2 − x1、max(0, ·) 钳零、相接记 0。
易错点展开
- 压制条件写成 >=:边界组专门卡这个。
- 同分不按下标处理:结果不可复现。
- 用了「两两压制」而不是「保留者压制」:链式场景直接错。
- 输出排序后的位置而不是原始下标。
参考实现怎么读
参考实现分三步:读入后建 order = sorted(range(n), key=(-score, i));removed = [False]*n;按 order 走主循环,保留者与其后每个未处理框算一次 IoU,严格大于 T 就标记 removed。IoU 函数与上一题同一份,复用即可。O(N²) 在 N ≤ 300 下毫无压力,别为这个规模写什么优化。
写完先自查这三组
1. 示例 2 的链式:0 压 1 后,1 不再压 2,输出 0 2——两两互压版会输出 0。 2. 三个完全相同的框、同分:按下标处理,0 压掉 1、2,输出 0。 3. T = 1:任何两框 IoU ≤ 1 都不严格大于 1,谁也压不掉谁,全保留、按分数序输出。
「严格大于」和「保留者压制」两条规则各有用例专门在卡,自查时盯这两条。
和课程的连接
排序键里的「同分下标小者优先」是这门课从第 2 天 Top K 就立下的并列传统,到检测后处理仍然是同一条纪律:输出必须可复现,规则必须写进代码而不是靠运气。压制循环的「丢掉确定不要的」也和第 5 天双指针的交换论证同一个气质——每一步丢弃都有明确理由。
参考代码
# NMS 贪心:按(分数降序,下标升序)处理,保留者压掉 IoU 严格大于 T 的未处理框
# 被压掉的框不再压别人(链式);输出原始下标、按保留顺序
import sys
def main():
data = sys.stdin.buffer.read().split()
at = 0
n = int(data[at]); at += 1
thr = float(data[at]); at += 1
boxes = []
scores = []
for _ in range(n):
boxes.append((float(data[at]), float(data[at + 1]), float(data[at + 2]), float(data[at + 3])))
scores.append(float(data[at + 4]))
at += 5
order = sorted(range(n), key=lambda i: (-scores[i], i))
removed = [False] * n
keep = []
for oi in range(len(order)):
i = order[oi]
if removed[i]:
continue
keep.append(i)
bi = boxes[i]
for oj in range(oi + 1, len(order)):
j = order[oj]
if removed[j]:
continue
bj = boxes[j]
ix = min(bi[2], bj[2]) - max(bi[0], bj[0])
if ix < 0.0:
ix = 0.0
iy = min(bi[3], bj[3]) - max(bi[1], bj[1])
if iy < 0.0:
iy = 0.0
inter = ix * iy
uni = (bi[2] - bi[0]) * (bi[3] - bi[1]) + (bj[2] - bj[0]) * (bj[3] - bj[1]) - inter
iou = inter / uni if uni > 0.0 else 0.0
if iou > thr:
removed[j] = True
sys.stdout.write(" ".join(map(str, keep)) + "\n")
main()
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
