Python数组并集长度计算代码的时间复杂度验证及优化咨询

时间复杂度判断正误说明 #

你的判断是错误的，实际时间复杂度远高于O(n+m)，原因如下：

• Python中列表的in成员查询需要遍历整个列表，时间复杂度为O(m)（m为查询列表的长度）
• 列表的remove操作需要先找到目标元素，再移动后续元素补位，时间复杂度同样是O(m)
• 你遍历了长度为n的短数组，每轮循环都要执行一次in查询和一次remove操作，整体时间复杂度为O(nm)*，属于平方级开销，数据规模稍大就会很慢。

同时你这段代码还有个隐藏问题：会直接修改传入的原数组对象，如果你后续还要用到原输入数组，数据会被篡改。

最优算法推荐 #

要达到O(n+m)的时间复杂度，用哈希集合实现是最优方案，集合的成员查询、插入操作均摊时间复杂度都是O(1)，完全满足要求：

class Solution :
    def getUnion(self,a,b):
        # 求两个集合的并集后返回长度
        return len(set(a) | set(b))

print(Solution().getUnion([1,2,3,4,5],[2,3,4,54,67]))

如果需要兼容多重集的并集统计（即保留重复元素的计数，比如a里有2个1，b里有3个1，并集里算3个1），可以用collections.Counter实现，开销同样是O(n+m)。

内容的提问来源于stack exchange，提问作者Bikash Cocboy