Meta 保序列表差集：筛掉第二列表元素

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 元素可hash且等值语义明确；这是按成员资格筛选，不是按出现次数相减。
• 第一列表中重复且未排除的值都保留；第二列表重复不改变排除集合。

解题路线

1. 先将second建set；扫first，若value不在set则append。first的访问顺序决定输出顺序，因此无需sort。
2. hashset只用于排除，不把first变set，否则会丢重复和顺序。列表成员逐个线性查second的基线为O(nm)。
3. 若对象不可hash，可用规范ID或定义比较key；不能随便序列化对象作为key而改变相等关系。

手动走一遍

first=[3,1,3,2,4]、second=[1,2,2]，结果[3,3,4]；不是去重后的[3,4]，也不是计数相减。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def stable_difference(first, second):
    excluded=set(second)
    return [value for value in first if value not in excluded]

复杂度

O(n+m)预期时间，O(U_second)排除集合空间，另加输出；恶意hash退化需依据实现讨论。

易错点与追问

容易失分的边界

• 集合差firstSet−secondSet不能保持顺序或first重复。
• 若业务要求多重集次数相减，使用Counter消费而非set，需明确不同合同。

继续深挖

• 数据量大不能装second时可用磁盘hash分区或索引；Bloom filter有假阳性不能单独保证精确结果。
• 若first是流，second已建set后可yield匹配元素，输出无需全保留内存。