
本文介绍一种线性时间复杂度的算法,用于反复识别并归约数组中首次出现的重复元素——通过移除首个重复项、将第二个重复项折半(向下取整),直至无重复或出现零值为止。
本文介绍一种线性时间复杂度的算法,用于反复识别并归约数组中首次出现的重复元素——通过移除首个重复项、将第二个重复项折半(向下取整),直至无重复或出现零值为止。
在处理大规模数据(如长度达 $10^5$)时,暴力双重扫描(如每轮遍历统计频次再定位索引)会导致 $O(n^2)$ 时间复杂度,极易超时。核心优化思路在于:避免多轮全局扫描,改用单次左到右遍历 + 哈希索引 + 即时归约。
算法思想
- 维护一个哈希表
index,记录当前尚未被标记删除的数值与其最右侧合法出现位置(即最新有效索引) 的映射; - 从左到右遍历数组,对每个元素
arr[i]:- 若
arr[i]已存在于index中,说明它是重复值(且index[arr[i]]指向其前一次出现位置); -
立即执行归约操作:将
arr[index[arr[i]]]标记为无效(如置为None),并将当前arr[i]更新为arr[i] // 2(整数地板除); - 由于折半后
arr[i]可能再次与已有值冲突(例如5 → 2后又遇到另一个2),需用while循环持续检查、归约,直到arr[i]不再重复或变为0; - 若
arr[i]变为0,根据题意立即终止流程,返回所有非None元素;
- 若
- 遍历结束后,过滤掉所有
None值,即得最终结果。
该策略确保每个元素最多被“触发归约”常数次(因每次折半至少减半,至多 $O(\log \text{max_val})$ 次),整体时间复杂度为 $O(n \log V)$($V$ 为初始最大值),实践中可视为 近似 $O(n)$,远优于原始 $O(n^2)$ 解法。
Python 实现(清晰版)
def solve(arr):
# 使用列表副本避免修改原输入
a = arr.copy()
index = {} # value -> latest valid index
for i in range(len(a)):
# 当前值已存在且未被删除 → 触发归约
while a[i] in index:
if a[i] == 0:
# 遇到0,立即终止
return [x for x in a if x is not None]
# 删除前一个出现位置的元素(置为None)
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标记删除而非实际remove(),避免数组移动开销(remove()平均 $O(n)$); -
索引有效性:
index始终只保存未被删除位置的映射,确保每次pop操作安全; -
零值提前终止:一旦某元素折半后为
0,按题意立即退出,无需继续处理后续元素; -
Java 移植提示:若需 Java 版本,可用
Integer[]替代int[]以支持null标记,并用HashMap存储索引;循环内注意空指针检查。
此方法兼顾正确性、效率与可读性,是处理此类“动态重复归约”问题的经典范式。










