难度: Medium
Submission
运行时间: 44 ms
内存: 16.6 MB
class Solution:
def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
cc = set(arrays[0])
for t in arrays[1:]:
cc = cc.intersection(Counter(t))
nums = list(cc)
nums.sort()
return nums
Explain
这个解法的思路是通过集合运算来找出所有给定数组中的公共元素。首先，它初始化一个集合 `cc` ，包含第一个数组的所有元素。随后，它遍历剩余的数组，并通过取交集操作更新 `cc` 集合，确保 `cc` 中只保留那些在所有数组中都出现的元素。最后，将得到的公共元素集合转换为列表，并对其进行排序，然后返回这个排序后的列表。
时间复杂度: O(kn)
空间复杂度: O(n)
class Solution:
def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
cc = set(arrays[0]) # 初始化 cc 为第一个数组的元素集合
for t in arrays[1:]: # 遍历剩余的数组
cc = cc.intersection(set(t)) # 更新 cc 为与当前数组的交集
nums = list(cc) # 将集合转换为列表
nums.sort() # 对列表进行排序
return nums # 返回排序后的结果
Explore
在处理多个数组的公共元素时，使用集合（Set）的主要优势在于其提供的高效的查找、插入和删除操作，这些操作的平均时间复杂度为O(1)。此外，集合内的元素是唯一的，自动去重，这对于寻找公共元素尤其有用。相对而言，列表（List）的查找和删除操作的时间复杂度为O(n)，并且列表包含重复元素，不适合直接用于寻找不重复的公共元素。而字典（Dictionary）虽然也提供O(1)的查找和插入操作，但相对于集合来说，使用字典处理公共元素问题会增加额外的复杂度，例如需要额外管理键值对，而集合则更为直接和高效。
将集合`cc`初始化为第一个数组的所有元素是一个合理的起始步骤，因为我们需要一个基准来与其它数组进行交集操作。这种方法的效率可能受到第一个数组大小的影响。如果第一个数组相对较大，则初始化和后续的交集操作可能会消耗更多时间。然而，这种影响通常是可控的，因为交集操作会逐渐减少集合`cc`中的元素数目，从而可能减少后续操作的负担。总的来说，这种方法在大多数情况下都是高效的，但如果第一个数组异常大且与其他数组的重合度低，算法的初始阶段可能会稍显低效。
使用`cc.intersection(set(t))`确实需要考虑数组元素数量极不均匀的情况。在极端情况下，如果某个数组的元素数量远小于其他数组，那么将其转换为集合并进行交集操作可能会比较高效，因为交集操作的复杂度与较小集合的大小成正比。然而，如果存在一个非常大的数组，这可能会导致初次构建集合时的效率降低，以及后续交集操作的处理时间增加。在实际应用中，针对数组元素数量极不均匀的情况，优化方法可以包括预先检测数组大小并调整算法策略，例如先对较小的数组进行交集操作，从而尽可能减少计算量和提高效率。