页面加载中…
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 <= N <= 300;0 <= T <= 1;坐标是至多一位小数的实数,-1000 <= 坐标 <= 1000,保证 x1 < x2、y1 < y2;分数是至多两位小数的实数,0 <= score < 1 或恰为整数 0/1;测试数据保证除刻意构造的边界组外,任意两框 IoU 与 T 的差的绝对值不小于 1e-9。
示例
示例 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 天双指针的交换论证同一个气质——每一步丢弃都有明确理由。
参考代码
# 十进制输入用 Fraction 精确比较：IoU 恰等于阈值时不能因浮点误差被错压
import sys
from fractions import Fraction
def main():
data = sys.stdin.buffer.read().split()
at = 0
n = int(data[at]); at += 1
threshold = Fraction(data[at].decode()); at += 1
boxes, scores = [], []
for _ in range(n):
values = [Fraction(x.decode()) for x in data[at:at + 5]]
boxes.append(tuple(values[:4]))
scores.append(values[4])
at += 5
order = sorted(range(n), key=lambda i: (-scores[i], i))
removed = [False] * n
keep = []
for pos, i in enumerate(order):
if removed[i]:
continue
keep.append(i)
a = boxes[i]
for j in order[pos + 1:]:
if removed[j]:
continue
b = boxes[j]
width = max(Fraction(0), min(a[2], b[2]) - max(a[0], b[0]))
height = max(Fraction(0), min(a[3], b[3]) - max(a[1], b[1]))
inter = width * height
union = (a[2]-a[0])*(a[3]-a[1]) + (b[2]-b[0])*(b[3]-b[1]) - inter
if inter > threshold * union:
removed[j] = True
sys.stdout.write(" ".join(map(str, keep)) + "\n")
main()
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
