删除第二数组冲突项：前K填满之前持续过滤

题意与假设

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

• 训练合同：list1至少K项；删除任意list2元素但保留顺序，结果至少K项，结果前K与list1前K按值不相交。
• 取最少删除的合法结果；若非冲突项不足K返回None。K=0返回原第二表副本。

解题路线

1. forbidden=set(list1[:K])。扫描list2，在填足K个保留项之前丢掉所有forbidden，其余保留并推进filled。
2. 填足K后，后面的值不再影响前K，全部原样保留。提前删除任何非forbidden都无助且增加删数，所以贪心最少。
3. 每个被删forbidden在找到第K个非冲突前都必须删：只要保留，它最终会出现在前K里。若始终找不够K，则不存在满足长度合同的方案。

手动走一遍

list1=[1,2],K=2,list2=[1,3,2,4,1]：依次删1、留3、删2、留4，前K已满，最后1保留，结果[3,4,1]。list2=[1,3]只一个非冲突项，K2无解，不能返回短表并声称成功。

Python 参考实现

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

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

def filter_prefix_conflicts(first, second, k):
    if k < 0 or len(first) < k:
        raise ValueError("nonnegative k required")
    forbidden = set(first[:k])
    result, filled = [], 0
    for x in second:
        if filled < k:
            if x in forbidden:
                continue
            filled += 1
        result.append(x)
    return result if len(result) >= k else None

复杂度

O(K+n)时间、O(K+n)空间含输出；in-place写指针可省输出副本，但仍需forbidden集合。

易错点与追问

容易失分的边界

• 过滤整张list2会多删前K之后的合法尾部项。
• 只删除原list2[:K]的冲突，未处理被推入前K的新冲突。

继续深挖

• 如果只能删前K而不能让后项补入，合同与结果怎样不同？
• 链表输入怎样边扫边删除并保留尾部？