需要统计「版本号 ≥ 基线」的个数。数据可达 105,不宜对每个元素反复扫描以外的低效做法;正解是:
versions 升序排序lower_bound)找到第一个 ≥baseline 的下标 lo也可以排序后暴力从左扫到第一个满足条件的位置,复杂度同为 O(nlogn) 主导;题解强调二分以体现查找思想。
漏洞库中记录了若干已安装补丁的版本号 versions(下标从 0 开始,未必有序)。安全基线为整数 baseline。
凡版本号 大于等于 baseline 的补丁,都视为「相对基线仍需纳入升级巡检」。
请返回需要纳入巡检的补丁数量。
请实现:
countNeedUpgrade(versions: int[], baseline: int) -> int
两行:
versions,形如 [1, 5, 3, 8, 5]baseline约束:
一个整数:版本号 ≥baseline 的个数。
输入:
[1, 5, 3, 8, 5]
5
输出:
3
说明:5,8,5 均 ≥5,共 3 个。
输入:
[2, 2, 2]
3
输出:
0
说明:全部小于基线。
输入:
[10]
10
输出:
1
说明:恰好等于基线也要计入。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册