
本文介绍一种时间复杂度为 o(n) 的数组约简算法,用于反复识别首个重复元素、移除其首次出现位置、并将第二次出现位置的值减半(向下取整),直至无重复或出现 0;适用于百万级数据规模。
本文介绍一种时间复杂度为 o(n) 的数组约简算法,用于反复识别首个重复元素、移除其首次出现位置、并将第二次出现位置的值减半(向下取整),直至无重复或出现 0;适用于百万级数据规模。
在处理大规模数组(如长度达 $10^5$)时,朴素双重遍历或每次重建哈希映射的 O(n²) 解法极易超时。关键优化在于:避免重复扫描,改用单次左到右遍历 + 即时冲突处理 + 延迟清理。
核心思想是:
- 维护一个
index映射(值 → 最近一次未被标记为“待删除”的索引); - 遍历每个位置
i时,若当前值arr[i]已存在于index中,说明发生重复 → 立即“逻辑删除”前一次出现的位置(将其置为None),并将arr[i]更新为arr[i] // 2; - 因为
arr[i]被减半后可能再次与更早的值冲突(如5→2,2→1,1→0),需用while循环持续检查,直到arr[i]不再重复或变为0; - 最终过滤掉所有
None元素,得到结果。
该策略确保每个元素最多被访问和修改常数次(每次 halving 至少减半,故单个元素最多触发 $O(\log \text{val})$ 次冲突处理),整体时间复杂度严格为 O(n log V),其中 V 是初始最大值(实际中可视为 O(n))。
以下是 Python 实现(清晰体现算法本质,可轻松迁移至 Java):
def solve(arr):
# 使用列表副本,避免修改原输入
a = arr.copy()
index = {} # value -> latest valid index (not None)
for i in range(len(a)):
# 若当前值已存在,持续处理冲突
while a[i] in index:
if a[i] == 0:
break # 遇到 0,立即终止
prev_idx = index.pop(a[i]) # 获取并移除旧索引
a[prev_idx] = None # 标记为删除
a[i] //= 2 # 当前值减半(整除)
# 更新当前值的最新有效索引(仅当非 None)
if a[i] is not None:
index[a[i]] = i
# 过滤 None,返回结果
return [x for x in a if x is not None]
# 测试
print(solve([2, 1, 5, 10, 10, 1])) # 输出: [0, 1]⚠️ 注意事项:
-
不可原地修改索引映射中的
None值:index中只存有效数值及其索引,None仅作为占位符,不参与哈希查找; -
整除使用
//(Python)或/后强转int(Java):题目隐含向下取整(如5//2=2,1//2=0),必须用整数除法; -
Java 移植建议:用
Map<integer integer></integer>替代dict,用ArrayList<integer></integer>存储,并以null或特殊哨兵值(如Integer.MIN_VALUE)标记已删项;但注意null不能作为HashMap键,因此推荐用布尔数组deleted[]单独记录删除状态,保持index映射纯净; -
边界安全:当
a[i] == 0时立即跳出while并结束整个流程,无需继续处理后续元素。
总结:本解法摒弃了“先统计再处理”的两阶段思维,转而采用“边走边压”的流式处理范式,将重复检测、删除、更新耦合于单次遍历中,既满足严苛的时间约束,又保持逻辑简洁与工程可读性。对于类似需多次迭代约简的数组问题,该模式具有普适参考价值。

















