题目重点:OA 第一题按数组中严格大于/小于 target 的元素数作三态判断,等于 target 不参与两边计数。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 输入为可比较的数值数组;与 target 相等的项不计入 greater/smaller。
- 返回英文小写 `greater`/`smaller`/`tie`;空数组两边为零,返回 tie。
- 数组中重复值按每个位置独立计数。
解题路线
- 分别初始化 greater=0、smaller=0,逐元素用严格 > 和 <;等于的直接跳过。
- 扫完比较两个计数并返回对应标签;只需要差值 delta 也可 +1/−1 累积,但双计数更便于解释。
- 验证所有值相等、空数组、重复元素、负数与两边计数相同。
手动走一遍
target=5、arr=[6,6,5,3] 时 greater=2、smaller=1,返回 greater;arr=[6,5,3] 两边各 1,返回 tie。
规模与取舍
n 个数字一次扫描 O(n) 时间、O(1) 空间。
易错点与追问
容易失分的边界
- 把等于 target 的值计入任一侧。
- 对 distinct 数值计数而不是按位置计数。
- 用数组总长度减大于数量推小于数量,误把相等项算进去。
继续深挖
- 数据流到来时如何 O(1) 更新三态?
- 比较阈值改为一段区间如何统计?
